#include <bits/stdc++.h>

using namespace std;

const int maxn=1000000+5;

const int maxm=10000+5;

char T[maxn],W[maxm];

void kmp_pre(char x[],int m,int nextp[])

{   //自身与自身进行匹配

    int i,j;

    i=0;

    j=nextp[0]=-1;

    while(i<m)

    {

        while(j!=-1 && x[i]!=x[j]) j=nextp[j];

        nextp[++i]=++j;

    }

}

int nextp[maxm];

int KMP_Count(char x[],int m,char y[],int n)

{   //x是模式串，y是主串

    int i,j;

    int ans=0;

    kmp_pre(x,m,nextp);

    i=j=0;

    while(i<n)

    {

        while(j!=-1 && y[i]!=x[j]) j=nextp[j];

        i++,j++;

        if(j>=m)

        {

            ans++;

            j=nextp[j];

        }

    }

    return ans;

}

int main()

{

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

    int t;

    scanf("%d",&t);

    while(t--)

    {

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

        printf("%d\n",KMP_Count(W,strlen(W),T,strlen(T)));

    }

    return 0;

}