#include<cstdio> #include<cstring> using namespace std; //KMP char str[1000005],sub[10005]; int next[10005]; int len_str,len_sub; void get_next() { int i = 0,j = -1; next[0] = -1; while(i<len_sub) { if(j==-1||sub[i]==sub[j]){ ++i; ++j; next[i] = j; } else j = next[j]; } } void KMP() { get_next(); int i = 0,j = 0,ans = 0; while(i<len_str&&j<len_sub) { if(j==-1||sub[j]==str[i]) { ++i; ++j; } else j = next[j]; if(j==len_sub) { ans++; j = next[j]; } } printf("%d\n",ans); } int main() { int n; scanf("%d",&n); getchar(); while(n--) { gets(sub); gets(str); len_str = strlen(str); len_sub = strlen(sub); KMP(); } return 0; }