> #include<iostream>
> #include<cstring>
> using namespace std;
> int next1[1000010];
> char aa[1000010];
> char bb[1000010];
> int n,m;
> void getnext(char a[])
> {
> 	int i=0,j=-1;
> 	next1[0]=-1;
> 	while(i<n)
> 	{
> 		if(j==-1 || a[j]==a[i])
> 		{
> 			++j;
> 			++i;
> 			if(a[i]!=a[j]) next1[i]=j;
> 			else next1[i]=next1[j];
> 		}
> 		else
> 		{
> 			j=next1[j];
> 		}
> 	}
> }
> int KMPindex(char b[],char a[],int pos)
> {
> 	int i=pos;
> 	int j=0;
> 	while(i<m && j<n)
> 	{
> 		if(j==-1 || b[i]==a[j])
> 		{
> 			++i;
> 			++j;
> 		}
> 		else j=next1[j];
> 	}
> 	if(j>=n)	return i-n+1;
> 	else return -1;
> }
> int main()
> {
> 	int x;
> 	cin>>x;
> 	while(x--)
> 	{
> 		int count=0;
> 	        cin>>aa;
> 	        getchar();
>  	        cin>>bb;
> 		n=strlen(aa);
> 		m=strlen(bb);
> 		getnext(aa);
> 		for(int i=0;i<m;i++)
> 		{
> 			i=KMPindex(bb,aa,i);
> 			if(i!=-1) 
> 			{
> 				count++;
> 			}
> 			else break;
> 		}
> 		cout<<count<<endl;
> 	}
> 	return 0;
> }