#include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #define N 1000005

 using namespace std;

 int next[N];

 char s1[N],s2[N];

 int len1,len2,ans;

 void getnext(int plen){

     int i = ,j = -;

     next[] = -;

     while( i<plen ){

         if(j==-||s1[i]==s1[j]){

             ++i;++j;

           if(s1[i]!=s1[j] )

             next[i] = j;

           else

             next[i] = next[j];

         }

         else

             j = next[j];

     }

 }

 void KMP(){

     getnext(len1);

     int i = ,j = ;

     while (i<len2&&j<len1){

         if( j == - || s2[i] == s1[j] ){

             ++i;

             ++j;

         }

         else {

             j = next[j];

         }

          if( j==len1 ){//找到一个匹配串之后，不是在原来串中往后移动一位，而是移动i-(j-next[j]);

             ans++;

             j=next[j];

          }

     }

 }

 int main(){

     int k;

     scanf("%d",&k);

     while(k--){

         scanf("%s%s",s1,s2);

         len1=strlen(s1);

         len2=strlen(s2);

         ans=;

         KMP();

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

     }

 }