#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>using namespace std;const int maxm = 1000005, maxn = 10005;char str[maxm + maxn], pat[maxn];int len, len1, len2;int kmp(){ int fail[maxn]; int i, j, k; memset(fail, -1, sizeof(fail)); for (i = 1; i < len2; ++i) { for (k = fail[i - 1]; k >= 0 && pat[i] != pat[k + 1]; k = fail[k]) ; if (pat[k + 1] == pat[i]) fail[i] = k + 1; } i = j = 0; int ans = 0; while (i < len) { if (pat[j] == str[i]) ++i, ++j; else if (j == 0) ++i; else { if (j == len2) ans++; j = fail[j - 1] + 1; } } if (j == len2) ans++; return ans;}int main(){ int t; scanf("%d", &t); while (t--) { scanf("%s", pat); scanf("%s", str); len1 =strlen(str); len2 =strlen(pat); len = len1; printf("%dn", kmp()); } return 0;}
