#include<iostream>

using namespace std;

const int MAXN = 1000012;

#ifndef _KMP_
#define _KMP_
int tcase,next[MAXN];
char s[MAXN],p[MAXN];

int KMP(char s[],char p[]);
void SetNextArray(char p[],int next[]);
#endif

int main()
{
    scanf("%d",&tcase);getchar();while(tcase--)
    {
        gets(s),gets(p);
        printf("%d\n",KMP(p,s));
    }
    return 0;
}

int KMP(char s[],char p[])
{
    SetNextArray(p,next);
    int cnt=0;
    for(int i=0,j=0,ls=strlen(s),lp=strlen(p);ls-i>0;)
    {
        if(j==-1||s[i]==p[j])
        {
            i++;
            j++;
        }
        else j=next[j];
        if(j==lp) cnt++;
    }
    return cnt;
}
void SetNextArray(char p[],int next[])
{
    memset(next,0,sizeof(next)); next[0]=-1;
    for(int i=0,j=-1,l=strlen(p);l-i>0;)
    {
        if(j==-1||p[i]==p[j])
        {
            i++;
            j++;
            next[i]=j;
        }
        else j=next[j];
    }
}