真麻了。今天一天都是在调题的路上。

RE 0pts，本地测下面注释里的手造样例也华丽RE，但是我寻思这数据里的串长不存在开小啊（
输出 dfs 过程也没什么问题。

请问是个什么原理啊\fad

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

#define ri register int
#define ll long long

inline void Cyprus(){
	ios::sync_with_stdio(0),
	cin.tie(0),cout.tie(0);
}

#define N 200005
char a[N>>1],b[N>>1],s[N]; int sa[N],rk[N],bac[N],y[N],tot;
int Log[N],st[N][18],ht[N],lena,lenb,tlen,res;
void Height(int n){
	for(ri i=1,k=0;i<=n;++i){
		if(k) --k; ri j=sa[rk[i]-1]; while(s[i+k]==s[j+k]) ++k;
		ht[rk[i]]=st[rk[i]][0]=k;
	}
}
bool same(int a,int b,int k){ return y[a]==y[b]&&y[a+k]==y[b+k]; }
void SA(int n,int m){
	for(ri i=1;i<=n;++i) ++bac[rk[i]=s[i]];
	for(ri i=2;i<=m;++i) bac[i]+=bac[i-1];
	for(ri i=n;i;--i) sa[bac[rk[i]]--]=i;
	for(ri k=1;k<=n;m=tot,tot=0,k<<=1){
		for(ri i=n;i>n-k;--i) y[++tot]=i;
		for(ri i=1;i<=n;++i) if(sa[i]>k) y[++tot]=sa[i]-k;
		for(ri i=1;i<=m;++i) bac[i]=0;
		for(ri i=1;i<=n;++i) ++bac[rk[i]];
		for(ri i=2;i<=m;++i) bac[i]+=bac[i-1];
		for(ri i=n;i;--i) sa[bac[rk[y[i]]]--]=y[i],y[i]=0;
		swap(rk,y),tot=rk[sa[1]]=1;
		for(ri i=2;i<=n;++i) rk[sa[i]]=(tot+=1-same(sa[i],sa[i-1],k));
		if(tot==n) break;
	} Height(n);
}
void make_table(int n){
	Log[0]=Log[1]=0; for(ri i=2;i<=n;++i) Log[i]=Log[i>>1]+1;
	for(ri i=n;i;--i) for(ri k=1;i+(1<<k)-1<=n;++k) st[i][k]=min(st[i][k-1],st[i+(1<<k-1)][k-1]);
}
int query(int l,int r){ ri k=Log[r-l+1]; return min(st[l][k],st[r-(1<<k)+1][k]); }
int Lciop(int a,int b){ return query(min(rk[a],rk[b])+1,max(rk[a],rk[b])); }
void dfs(int pa,int pb,int step){
	if(step>3) return;
	if(pa==lena+1){ res+=(pb==lenb+1); return; }
	int lcp=Lciop(pa,pb+lena+1); pa+=lcp,pb+=lcp;
	if(pa==lena+1){ res+=(pb==lenb+1); return; }
	if(pb==lenb+1){ ++res; return; }
	dfs(pa+1,pb+1,step+1);
}
void relive(){
	res=tot=0;
	for(ri i=1;i<=lena;++i) a[i]=0;
	for(ri i=1;i<=lenb;++i) b[i]=0;
	for(ri i=1;i<=tlen;++i)
		rk[i]=sa[i]=ht[i]=bac[i]=y[i]=s[i]=0;
	lena=lenb=tlen=0;
}
void debug(){
	cout<<"Debugging : "<<endl;
	for(ri i=1;i<=tlen;++i){
		ri ptr=sa[i]; cout<<"the "<<i<<" th : ";
		while(s[ptr]) cout<<s[ptr]<<' ',++ptr; cout<<endl;
	}
}

int main()
{
	Cyprus(); int T; cin>>T; while(T--){
		cin>>a+1,lena=strlen(a+1);
		cin>>b+1,lenb=strlen(b+1);
		if(lena<lenb){ cout<<0<<endl; continue; }
		for(ri i=1;i<=lena;++i) s[i]=a[i]; s[lena+1]='A'-1;
		for(ri i=1;i<=lenb;++i) s[lena+1+i]=b[i]; tlen=lena+1+lenb;
		for(ri i=1;i<=tlen;++i) cout<<s[i]<<(i==tlen?'\n':' ');
		SA(tlen,86),make_table(tlen); debug();
		for(ri i=1;i<=lena-lenb+1;++i) dfs(i,1,0);
		cout<<res<<endl; relive();
	}
	return 0;
}
/*
4
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
TTTTTTTT
ACGTGTGTGTTGTGTGGTGT
GTGTG
ACGTGTGTGTTGTGTGGTGTACGGGGTTTAAACCGG
ACGCGG
ACGTGTGTGTTGTGTGGTGTTTTTTTTTTTTTTTTTTTTTTTTACG
GTGTG
*/