#include<algorithm>

#include<iomanip>

#include<cstring>

#include<string>

#include<cstdio>

#include<cmath>

using namespace std;

#define il inline

#define gc getchar()

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

const int N=+;

int nxt[N];

char w[N],t[N];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il void getnxt()

{

    ri lth=strlen(w+);

    rp(i,,lth)

    {

        ri nw=nxt[i-];

        while(nw && w[nw+]!=w[i])nw=nxt[nw];

        if(w[nw+]==w[i])++nw;nxt[i]=nw;

    }

}

il int kmp()

{

    ri lthw=strlen(w+),ltht=strlen(t+),i=,j=,as=;

    while(j<=ltht)

    {

        if(w[i]==t[j]){++i;++j;if(i==lthw+)++as,i=nxt[i-]+;}

        else if(i==)++j;else i=nxt[i-]+;

    }

    return as;

}

int main()

{

//    freopen("3461.in","r",stdin);freopen("3461.out","w",stdout);

    ri T=read();

    while(T--)

    {

        memset(nxt,,sizeof(nxt));

        scanf("%s",w+);scanf("%s",t+);

        getnxt();printf("%d\n",kmp());

    }

    return ;

}

#include<algorithm>

#include<iomanip>

#include<cstring>

#include<string>

#include<cstdio>

#include<cmath>

using namespace std;

#define il inline

#define gc getchar()

#define ri register int

#define rb register bool

#define rc register char

#define ll unsigned long long

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

const int N=+,bas=;

int lth_w,lth_t;

ll w_hsh,t_hsh[N],poww;

char w[N],t[N];

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

il ll power(ri gd,ri gs){ll ret=;while(gs){if(gs&)ret=1ll*ret*gd;gd=1ll*gd*gd;gs>>=;}return ret;}

int main()

{

//    freopen("3461.in","r",stdin);freopen("3461.out","w",stdout);

    ri T=read();

    while(T--)

    {

        ri as=;w_hsh=;poww=;

        scanf("%s",w+);scanf("%s",t+);lth_w=strlen(w+);lth_t=strlen(t+);

        rp(i,,lth_w)w_hsh=1ll*w_hsh*bas+w[i];

        rp(i,,lth_t)t_hsh[i]=1ll*t_hsh[i-]*bas+t[i];

        //poww=power(bas,lth_w);

        rp(i,,lth_w)poww=poww*bas;

        rp(i,lth_w,lth_t)if(w_hsh==t_hsh[i]-t_hsh[i-lth_w]*poww)++as;

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

    }

    return ;

}