题目描述

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

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

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

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

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

输入

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

对于每组数据：

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

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

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

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

输出

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

样例 #1

样例输入#1

1
10 3
aabcaacbaa
abc

样例输出#1

4

样例 #2

样例输入#2

3
3 2
abc
ac
6 4
aabbcc
abc
12 6
abcdefabcdef
abcdef

样例输出#2

0
0
7