#include<iostream>
#include<string>
#include<string.h>
using namespace std;
char substr[10010];
char str[1000010];
int next[10010];
int kmp(){
	int count=0;
	int len=strlen(str);
	int len2=strlen(substr);
	for(int i=0,j=0;i<len;){
		if(j==-1||str[i]==substr[j]){
			++i;++j;
		}
		else{
			j=next[j];
		}
		if(j==len2){
			count++;
			j=next[j];
		}
	}
	return count;
}
void get_next(){
	memset(next,0,10010*sizeof(int));
	next[0]=-1;
	int len=strlen(substr);
	for(int i=0,j=-1;i<len;){
		if(j==-1 ||substr[j]==substr[i]){
			++i;++j;
			next[i]=j;
		}
		else{
			j=next[j];
		}
	}
}
int main(){
	int N;
	cin>>N;
	while(N--){
		cin>>substr>>str;
		get_next();
		cout<<kmp()<<endl;
	}
	return 0;
}