//    hdu 1686 KMP模板

 //    没啥好说的，KMP裸题，这里是MP模板

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int MAX_N = ;

 const int MAX_M = ;

 char T[MAX_N];

 char p[MAX_M];

 int f[MAX_M];

 int n,m;

 void getfail(){

     f[] = f[] = ;

     for (int i=;i<m;i++){

         int j = f[i];

         while(j && p[i]!=p[j])

             j = f[j];

         f[i+] = (p[i]==p[j]) ? j +  : ;

     }

 }

 int cmp(){

     int cnt = ;

     int j = ;

     for (int i=;i<n;i++){

         while(j && T[i] != p[j])

             j = f[j];

         if (T[i] == p[j])

             j++;

         if (j==m){

             cnt++;

         }

     }

     return cnt;

 }

 int KMP(){

     getfail();

     return cmp();

 }

 void input(){

     scanf("%s%s",p,T);

     n = strlen(T);

     m = strlen(p);

     printf("%d\n",KMP());

 }

 int main(){

     int t;

     //freopen("1.txt","r",stdin);

     scanf("%d",&t);

     while(t--){

         input();

     }

 }