#include<bits/stdc++.h>
using namespace std;
const int N=1110000;
char sa[N], sb[N];
int pre[N];

int main() 
{
    int T;scanf("%d", &T);
    while(T--) 
	{
        scanf("%s", sa+1);scanf("%s", sb+1);
        int lena=strlen(sa+1), lenb=strlen(sb+1);
        memset(pre, 0, sizeof(pre));
        for(int i=1, j=pre[i]; i<lena; i++, j=pre[i]) 
		{
            while( j>0 && sa[i+1]!=sa[j+1]) j=pre[j];
            if(sa[i+1]==sa[j+1])pre[i+1]=j+1;
        }
        int ans=0;
        for(int i=0, j=0; i<lenb; i++) 
		{
            while( j>0 && sb[i+1]!=sa[j+1]) j=pre[j];
            if(sb[i+1]==sa[j+1]) j++;
            if(j==lena) ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}