> #include<cstdio>
> #include<cstdlib>
> #include<cstring>
> #include<iostream>
> using namespace std;
> 
> int n,la,lb;
> int next[100010];
> char a[1000010],b[100010];
> 
> void getnext()
> {
> 	int j=-1;
> 	next[0]=-1;
> 	for(int i=1;i<lb;i++)
> 	{
> 		if(j!=-1 && b[j+1]!=b[i])	j=next[j];
> 		if(b[j+1]==b[i])	j++;
> 		next[i]=j;
> 	}
> }
> 
> int kmp()
> {
> 	int ans=0;
> 	int j=-1;
> 	for(int i=0;i<la;i++)
> 	{
> 		if(j!=-1 && a[i]!=b[j+1])	j=next[j];
> 		if(b[j+1]==a[i])	j++;
> 		if(j==lb-1)	
> 		{
> 			ans++;	
> 			j=next[j];
> 		}	
> 	}
> 	return ans;
> }
> 
> int main()
> {
> 	scanf("%d",&n);
> 	for(int u=1;u<=n;u++)
> 	{
> 		scanf("%s %s",b,a);
> 		la=strlen(a);
> 		lb=strlen(b);
> 		getnext();
> 		printf("%d\n",kmp());
> 	}
> }