求T串中包含了几个P串//裸的kmp题，试一下自己的模板
#include<iostream>
#include<cstring>
#include<string.h>
#include<cstdio>
#include<cstdlib>
using namespace std;
void kmp_pre(char x[],int m,int next[])
{int i,j;j=next[0]=-1;i=0;while(i<m){while(-1!=j&&x[i]!=x[j]) j=next[j];next[++i]=++j;}
}
//返回x在y中出现的次数，可以重叠
int next[1000010];
int KMP_Count(char x[],int m,char y[],int n)
{int i,j;int ans=0;kmp_pre(x,m,next);i=j=0;while(i<n){while(j!=-1&&y[i]!=x[j]) j=next[j];i++;j++;if(j>=m){ans++;j=next[j];}}return ans;
}
int main()
{int k;scanf("%d",&k);while(k--){char xx[1000000+100],yy[1000000+100];scanf("%s%s",yy,xx);int cm=strlen(yy);int cn=strlen(xx);int cnt=0;cnt=KMP_Count(yy,cm,xx,cn);printf("%d\n",cnt);}return 0;
}