#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdio>

#define M 10050

#define N 1005000

using namespace std;

int next1[M];

char s[N];

char t[M];

int slen,tlen;

void  get_next()

{

    int j=0,k=-1;

    next1[0]=-1;

    while(j<tlen)

    {

        if(k==-1||t[j]==t[k])

        {

            next1[++j]=++k;

        }

        else

            k=next1[k];

    }

}

int kmp_cnt()

{

    int ans=0,i=0,j=0;

    if(slen==1&&tlen==1)

    {

        if(s[0]==t[0])

            return 1;

        else

            return 0;

    }

    get_next();

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

    {

        while(j>0&&s[i]!=t[j])

            j=next1[j];

        if(s[i]==t[j])

            j++;

        if(j==tlen)

        {

            ans++;

            j=next1[j];

        }

    }

    return ans;

}

int main()

{

    ios::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

    int tt;

    cin>>tt;

    while(tt--)

    {

        cin>>t;

        cin>>s;

        tlen=strlen(t);

        slen=strlen(s);

        cout<<kmp_cnt()<<endl;

    }

}