//poj3461 Oulipo

//kmp模板 统计子串在母串中的位置

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int next[];

char p[],s[];

int t,num,l1,l2;

void get_next()

{

    int j=;

    int k=-;

    next[]=-;

    while(j<l2)

    {

        if(k==-||p[k]==p[j])

        {

            k++;

            j++;

            next[j]=k;

        }

        else

        {

            k=next[k];

        }

    }

}

int kmp()

{

    int i=;

    int j=;

    get_next();

    while(i<l1)

    {

        if(j==-||p[j]==s[i])

        {

            j++;

            i++;

        }

        else

        {

            j=next[j];

        }

        if(j==l2)

        {

            num++;

            j=next[j];

        }

    }

    return num;

}

int main()

{

    cin>>t;

    while(t--)

    {

        num=;

        cin>>p>>s;

        l1=strlen(s);

        l2=strlen(p);

        cout<<kmp()<<endl;

    }

}

//洛谷3375 字符串匹配

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int next[];

string p,s;

void get_next(string p)

{

    next[]=-;

    int j=;

    int k=-;

    int l=p.length();

    while(j<l)

    {

        if(k==-||p[j]==p[k])

        {

            j++;

            k++;

            next[j]=k;

        }

        else

        {

            k=next[k];

        }

    }

}

void kmp(string s,string p)

{

    get_next(p);

    int i=,j=;

    int l=s.length();

    while(i<l)

    {

        if(j==-||p[j]==s[i])

        {

          i++;

          j++;

        }

        else

        {

            j=next[j];

        }

        if(j==p.length())

        {

            printf("%d\n",i-p.length()+);

            j=,i--;

        }

    }

    for(int a=;a<=p.length();a++)

    {

        cout<<next[a]<<" ";

    }

    return;

}

int main()

{

    cin>>s>>p;

    kmp(s,p);

}