#include<bits/stdc++.h>
using namespace std;
const int N=1e6+9;

char cs[N],ct[N];
int n,m,s[N],t[N],pre[29],nxt[N];

bool same(int a,int b,int j) {
	if(a<0||b<0) return a==b;			//大写字母
	return a==b||(b==0&&a>j);			//小写字母 
}
void kmp() {
	int j=0,ans=0; nxt[1]=0;
	for(int i=1;i<m;i++) {
		while(j&&!same(t[i+1],t[j+1],j)) j=nxt[j];
		if(same(t[i+1],t[j+1],j)) j++;
		nxt[i+1]=j;
	}
	j=0;
	for(int i=0;i<n;i++) {
		while(j&&!same(s[i+1],t[j+1],j)) j=nxt[j];
		if(same(s[i+1],t[j+1],j)) j++;
		if(j==m) ans++,j=nxt[j];
	}
	printf("%d\n",ans);
}

int main() {
	int Q; cin>>Q;
	while(Q--) {
		memset(ct,0,sizeof(ct)), memset(cs,0,sizeof(cs));
		memset(t,0,sizeof(t)), memset(s,0,sizeof(0));
		scanf("%s%s",cs+1,ct+1); n=strlen(cs+1), m=strlen(ct+1);
		memset(pre,0,sizeof(pre));
		for(int i=1;i<=n;i++)				//预处理s串 
			if(cs[i]>='a'&&cs[i]<='z')
				s[i]=(pre[cs[i]-'a'+1]>0 ? i-pre[cs[i]-'a'+1] : 0),
				pre[cs[i]-'a'+1]=i;
			else s[i]=-(cs[i]-'A'+1);		//大写字母记为负数
		memset(pre,0,sizeof(pre));
		for(int i=0;i<=m;i++)				//预处理t串 
			if(ct[i]>='a'&&ct[i]<='z')
				t[i]=(pre[ct[i]-'a'+1]>0 ? i-pre[ct[i]-'a'+1] : 0),
				pre[ct[i]-'a'+1]=i;
			else t[i]=-(ct[i]-'A'+1);
		kmp();
	}
	return 0;
}