#include <cstdio>
#include <memory.h>
using namespace std;
char text[1000005];
char pattern[10005];
int mnext[10005];

void getNext(char *s,int len)
{
	memset(mnext,0,sizeof(mnext));
	mnext[0]=-1;
	int i=0;
	int j=-1;
	while(i<=len-1)
	{
		if(j==-1||s[i]==s[j])
		{
			i++;
			j++;
			mnext[i]=j;
		}
		else
			j=mnext[j];
	}
}
int kmpCount(char *da,char* xiao,int tlen,int plen)
{
	int i=0;
	int j=0;
	int result=0;
	while(i<=tlen-1)
	{
		if(j==-1||da[i]==xiao[j])
		{
			i++;
			j++;
		}
		else
			j=mnext[j];
		if(j==plen)
			result++;
	}
	return result;
	

}
int main()
{
	int rounds;
	scanf("%d",&rounds);

	while(rounds--)
	{
		scanf("%s",pattern);
		scanf("%s",text);
		
		int tlen=0;
		int plen=0;
		for(;text[tlen]!='\0';tlen++);
		for(;pattern[plen]!='\0';plen++);
		getNext(pattern,plen);
		int result=kmpCount(text,pattern,tlen,plen);
		printf("%d\n",result);
		memset(pattern,0,sizeof(pattern));
		memset(text,0,sizeof(text));
	}
	return 0;
}