#include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxl=+;

 const int maxw=+;

 char t[maxl],p[maxw];

 int T,ans,f[maxw];

 void getfail(char *p)

 {

     int m=strlen(p);

     f[]=;f[]=;

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

     {

         int j=f[i];

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

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

     }

 }

 void kmp(char *t,char *p)

 {

     int n=strlen(t),m=strlen(p);

     getfail(p);

     int j=;

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

     {

         while(j&&p[j]!=t[i])  j=f[j];//printf("--\n");}

         if(p[j]==t[i])  j++;

         if(j==m)  ans++;

     }

 }

 int main()

 {

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

     scanf("%d",&T);

     while(T--)

     {

         ans=;

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

         kmp(t,p);

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

     }

     return ;

 }