#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

typedef unsigned long long ull;

const int N=1e5+;

int lena,lenb;

ull pin[N],haa[N],hab[N];

char a[N],b[N];

void H()

{

    haa[]=hab[]=;

    for (int i=;i<=lena;i++)

    {

        haa[i]=haa[i-]*+a[i]-'a';

    }

    for (int i=;i<=lenb;i++)

    {

        hab[i]=hab[i-]*+b[i]-'a';

    }

}

int solve(int x,int y)

{

    int l=,r=lenb;

    while (l<r)

    {

        int mid=l+r>>;

        if ((haa[x+mid-]-haa[x-]*pin[mid])==(hab[y+mid-]-hab[y-]*pin[mid]))

        {

            l=mid+;

        }

        else r=mid;

    }

    if (haa[x+l-]-haa[x-]*pin[l]!=hab[y+l-]-hab[y-]*pin[l])

    {

        return l;

    }

    else return l+;

}

int check(int x)

{

    int now=,k;

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

    {

        k=solve(x,now);

        //printf("%d %d %d\n",x,now,k);

        x+=k;now+=k;

        if (now>lenb) return ;

    }

    k=solve(x,now);

    x+=k-;now+=k-;

    if (now>=lenb) return ;

    return ;

}

int main()

{

    pin[]=;

    for (int i=;i<=N;i++) pin[i]=pin[i-]*;

    int T;

    scanf("%d",&T);

    while (T--)

    {

        scanf("%s",a+);

        scanf("%s",b+);

        lena=strlen(a+),lenb=strlen(b+);

        H();

        //printf("%d\n",solve(2,3));

        int re=;

        for (int i=;i<=lena-lenb+;i++)

        {

            if (check(i)) re++;

        }

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

    }

    return ;

}