#include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int maxn1 =  + ;

 const int maxn2 =  + ;

 char W[maxn1], T[maxn2];

 int next[maxn1];

 void get_next(char* W, int l)

 {

     int k = -, j = ;

     next[] = -;

     while(j < l)

     {

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

         {

             ++k;

             ++j;

             next[j] = k;

         }

         else k = next[k];

     }

 }

 int KMP(char* W, int lenw, char* T, int lent)

 {

     int i = , j = , ans = ;

     while(i < lent)

     {

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

         {

             ++i;

             ++j;

         }

         else j = next[j];

         if(j == lenw)

         {

             ans++;

             j = next[j];

         }

     }

     return ans;

 }

 int main()

 {

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

     int kase;

     scanf("%d", &kase);

     while(kase--)

     {

         memset(next, , sizeof(next));

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

         int lenw = strlen(W);

         int lent = strlen(T);

         get_next(W, lenw);

         printf("%d\n", KMP(W, lenw, T, lent));

     }

     return ;

 }