#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1000005;
int n, ans, next[N];
char str1[N], str2[N];
signed main(void) {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%s", str1); int len1 = strlen(str1);
		scanf("%s", str2); int len2 = strlen(str2);
		memset(next, 0, sizeof(next)), ans = 0;
		for (int i = 1, j = 0; i < len1; i++) {
			while (j > 0 && str1[i] != str1[j])j = next[j];
			if (str1[i] == str1[j])j++;
			next[i + 1] = j;
		}
		for (int i = 0, j = 0; i < len2; i++) {
			while (j > 0 && str1[j] != str2[i])j = next[j];
			if (str1[j] == str2[i])j++;
			if (j == len1)ans++, j = next[j];
		}
		printf("%d\n", ans);
	}
}