//unordered_set을 사용해서 C++11로 컴파일해야 합니다.
#include <cstdio>
#include <algorithm>
#include <unordered_set>
using namespace std;
int n, m, X[222];
char P[1000005], Q[105];
long long F[4];
char ss[5] = { 'A', 'C', 'G', 'T' };
int main() {
X['A'] = 0; X['C'] = 1; X['G'] = 2; X['T'] = 3;
int T;
for (scanf("%d", &T); T--;) {
scanf("%d%d\n", &n, &m);
gets(P); gets(Q);
if (n < m) { puts("0"); continue; }
for (int i = 0; i < 4; i++) {
F[i] = (int)(ss[i]);
for (int j = 0; j < m - 1; j++) F[i] = (F[i] * 257);
}
unordered_set <long long> h;
long long val;
int x;
for (int i = 0; i <= m; i++) {
for (int j = i; j <= m; j++) {
reverse(Q + i, Q + j);
val = 0;
for (int k = 0; k < m; k++) x = Q[k], val = (val * 257 + x);
h.insert(val);
reverse(Q + i, Q + j);
}
}
val = 0;
for (int i = 0; i < m; i++) x = P[i], val = (val * 257 + x);
int res = 0;
for (int i = m - 1; i < n; i++) {
if (h.count(val)) res++;
if (i < n - 1) val = (val - F[X[P[i - m + 1]]]) * 257 + P[i + 1];
}
printf("%d\n", res);
}
}
Ly91bm9yZGVyZWRfc2V07J2EIOyCrOyaqe2VtOyEnCBDKysxMeuhnCDsu7TtjIzsnbztlbTslbwg7ZWp64uI64ukLgojaW5jbHVkZSA8Y3N0ZGlvPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8dW5vcmRlcmVkX3NldD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IG4sIG0sIFhbMjIyXTsKY2hhciBQWzEwMDAwMDVdLCBRWzEwNV07CmxvbmcgbG9uZyBGWzRdOwpjaGFyIHNzWzVdID0geyAnQScsICdDJywgJ0cnLCAnVCcgfTsKaW50IG1haW4oKSB7CiAgWFsnQSddID0gMDsgWFsnQyddID0gMTsgWFsnRyddID0gMjsgWFsnVCddID0gMzsKCWludCBUOwoJZm9yIChzY2FuZigiJWQiLCAmVCk7IFQtLTspIHsKCQlzY2FuZigiJWQlZFxuIiwgJm4sICZtKTsKCQlnZXRzKFApOyBnZXRzKFEpOwoJCWlmIChuIDwgbSkgeyBwdXRzKCIwIik7IGNvbnRpbnVlOyB9CgkJZm9yIChpbnQgaSA9IDA7IGkgPCA0OyBpKyspIHsKCQkJRltpXSA9IChpbnQpKHNzW2ldKTsKCQkJZm9yIChpbnQgaiA9IDA7IGogPCBtIC0gMTsgaisrKSBGW2ldID0gKEZbaV0gKiAyNTcpOwoJCX0KCQl1bm9yZGVyZWRfc2V0IDxsb25nIGxvbmc+IGg7CgkJbG9uZyBsb25nIHZhbDsKCQlpbnQgeDsKCQlmb3IgKGludCBpID0gMDsgaSA8PSBtOyBpKyspIHsKCQkJZm9yIChpbnQgaiA9IGk7IGogPD0gbTsgaisrKSB7CgkJCQlyZXZlcnNlKFEgKyBpLCBRICsgaik7CgkJCQl2YWwgPSAwOwoJCQkJZm9yIChpbnQgayA9IDA7IGsgPCBtOyBrKyspIHggPSBRW2tdLCB2YWwgPSAodmFsICogMjU3ICsgeCk7CgkJCQloLmluc2VydCh2YWwpOwoJCQkJcmV2ZXJzZShRICsgaSwgUSArIGopOwoJCQl9CgkJfQoJCXZhbCA9IDA7CgkJZm9yIChpbnQgaSA9IDA7IGkgPCBtOyBpKyspIHggPSBQW2ldLCB2YWwgPSAodmFsICogMjU3ICsgeCk7CgkJaW50IHJlcyA9IDA7CgkJZm9yIChpbnQgaSA9IG0gLSAxOyBpIDwgbjsgaSsrKSB7CgkJCWlmIChoLmNvdW50KHZhbCkpIHJlcysrOwoJCQlpZiAoaSA8IG4gLSAxKSB2YWwgPSAodmFsIC0gRltYW1BbaSAtIG0gKyAxXV1dKSAqIDI1NyArIFBbaSArIDFdOwoJCX0KCQlwcmludGYoIiVkXG4iLCByZXMpOwoJfQp9