#include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<math.h>

 #include<string.h>

 #include<vector>

 #include<queue>

 #include<iterator>

 #include<vector>

 #include<set>

 #define dinf 0x3f3f3f3f

 typedef long long ll;

 //const int Max=(1<<16)+10;

 using namespace std;

 #define SIZE 100000005

 const int N = ;

 int m_next[N];

 char S[N],T[N];

 int slen, tlen;

 void getNext()

 {

     int j, k;

     j = ; k = -; m_next[] = -;

     while(j < tlen)

         if(k == - || T[j] == T[k])

             m_next[++j] = ++k;

         else

             k = m_next[k];

 }

 /*

 返回模式串T在主串S中首次出现的位置

 返回的位置是从0开始的。

 */

 int KMP_Index()

 {

     int i = , j = ;

     getNext();

     while(i < slen && j < tlen)

     {

         if(j == - || S[i] == T[j])

         {

             i++; j++;

         }

         else

             j = m_next[j];

     }

     if(j == tlen)

         return i - tlen+;

     else

         return -;

 }

 /*

 返回模式串在主串S中出现的次数

 */

 int KMP_Count()

 {

     int ans = ;

     int i, j = ;

     if(slen ==  && tlen == )

     {

         if(S[] == T[])

             return ;

         else

             return ;

     }

     getNext();

     for(i = ; i < slen; i++)

     {

         while(j >  && S[i] != T[j])

             j = m_next[j];

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

             j++;

         if(j == tlen)

         {

             ans++;

             j = m_next[j];

         }

     }

     return ans;

 }

 int main()

 {

     int TT;

     int i, cc;

     string str;

     cin>>TT;

     while(TT--)

     {

         getchar();

         scanf("%s %s",&T,&S);

         slen = strlen(S);

         tlen = strlen(T);

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

         //cout<<"模式串T在主串S中首次出现的位置是: "<<KMP_Index()/2+1<<endl;

         //cout<<"模式串T在主串S中出现的次数为: "<<KMP_Count()<<endl;

     }

     return ;

 }