#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char p[10005]={'a'};
char q[1000005]={'a'};

int kmp(void)
{
    int next[10005]={0};
    int i,j=2,lq,lp,k=0;
    
    next[1]=0;
    while (p[j] != '\0' )
    {
          i=next[j-1];
          while (i !=0 && p[i] != p[j-1]) 
          i=next[i];
          next[j]=i+1;
          j++;
          }
          
        lp=strlen(p)-1;
          i=1;j=0;
          
          lq=strlen(q)-1;
        j=0;
        
for (i=1;i<=lq;i++)
{
   while ( (j>0) && (p[j+1]!=q[i])) 
   j=next[j];
   if (p[j+1]==q[i]) j++;
   if (j==lp) 
  {
      k++;
      j=next[j];
}
}
         
         
    
    
    return k;
    
    }



int main()
{
    int m,i,k;
    
    scanf("%d",&m);
    for (i=1;i<=m;i++)
    {
        memset(p,'\0',sizeof(p));
        memset(q,'\0',sizeof(q));
        p[0]='a';
        q[0]='a';
        scanf("%s",&p[1]);
        scanf("%s",&q[1]);
        k=kmp();
        printf("%d\n",k);
        
        
        }
    
    
    
    
    return 0;
    
    }