hdu1686

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int n;
char w[10005], t[1000005];
int fail[10005];
int lenw, lent;

void getfail(){
	int x = -1;
	fail[0] = -1;
	for (int i = 1; i < lenw; i++){
		while(x >= 0 && w[i] != w[x + 1]){
			x = fail[x];
		}
		if(w[i] == w[x + 1]) x++;
		fail[i] = x;
	}
}

void KMP(){
	int x = -1;
	int ans = 0;
	for (int i = 0; i < lent; i++){
		while(x >= 0 && t[i] != w[x + 1]){
			x = fail[x];
		}
		if(t[i] == w[x + 1]){
			x++;
			if(x == lenw - 1) ans++;
		}
	}
	printf("%d\n", ans);
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &n);
	while(n--){
		scanf("%s %s", w, t);
		lenw = strlen(w), lent = strlen(t);
		getfail();
		KMP();
	}

	return 0;
}
/**/