该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

徐老师准备了一组小写字母磁贴，并把它们依次吸在黑板的长条区域中，形成字符串 $s$。

她手中还有一个长度为 $m$ 的口令 $p$。徐老师会用一个恰好能框住 $m$ 个连续磁贴的方框，从左向右移动。

如果方框中的磁贴经过重新排列后，能够恰好组成口令 $p$，那么方框当前所在的位置称为一个有效位置。

例如，口令为 abc 时，abc、bca 和 cab 都能组成该口令，而 abb 不能。

请计算方框共有多少个有效位置。

Format

Input

第一行一个正整数 $T$（$1 \leq T \leq 10$），表示测试组数。

对于每组数据：

第一行两个正整数 $n,m$（$1 \leq m \leq n \leq 10^5$）。

第二行一个长度为 $n$、仅由小写英文字母组成的字符串 $s$，表示黑板上的磁贴。

第三行一个长度为 $m$、仅由小写英文字母组成的字符串 $p$，表示口令。

所有测试组的 $n$ 之和不超过 $10^6$。

Output

对于每组数据，输出一行一个整数，表示有效位置的数量。

Samples

2
8 3
abcbacaa
abc
4 2
abba
ab

3
2

Limitation

1s, 1024KiB for each test case.