# include <stdio.h>

# include <algorithm>

# include <string.h>

using namespace std;

char a1[1000010],a2[1000010];

int next[1000010];

int len1,len2,cot;

void Getnext()

{

    int i=0,j=-1;

    next[0]=-1;

    while(i<=len1)

    {

        if(j==-1||a1[i]==a1[j])

            i++,j++,next[i]=j;

        else

            j=next[j];

    }

}

void KMP()

{

    int i,j;

    j=0;

    for(i=0; i<len2;)

    {

        if(a2[i]==a1[j]||j==-1)

        {

            i++;

            j++;

            if(j==len1)

            {

               // i-=len1-1;

               //j=0;

                j=next[j];//这步运用next~~~~

                cot++;

            }

        }

        else

            j=next[j];

    }

}

int main()

{

    int t;

    scanf("%d",&t);

        while(t--)

        {

            scanf("%s",a1);

            scanf("%s",a2);

            len1=strlen(a1);

            len2=strlen(a2);

            Getnext();

            cot=0;

            KMP();

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

        }

    return 0;

}