C++ :

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<bitset>
using namespace std;
const int N=17,M=50,gow1=(1<<18)-1;
int A[21],B[21],n,K,C[100],preK,fir[100],zerobit;
int go[4][1<<18],pd[1<<18];
long long f[2][1<<18],L,R,m,Lim[70],checkB;
char ch[30];
void preget(int K){
	long long x=0,y=0; int k1=K;
	for (int i=0;i<=N;i++){
		x|=(1ll*(k1&1)<<(i<<1)); k1>>=1;
	}
	pd[K]=(((x^checkB)>>zerobit)==0);
	go[0][K]=((x>>N)&gow1);
	go[1][K]=((x>>N+1)&gow1);
	for (int i=0;i<=n;i++) if (A[i]) y^=(x<<i);
	go[2][K]=((y>>N)&gow1);
	go[3][K]=((y>>N+1)&gow1);
	
}
long long solve(long long m,long long lim){
	if (lim==0) return 0;
	Lim[0]=lim;
	for (int i=1;i<=60;i++) Lim[i]=(Lim[i-1]+1)>>1;
	memset(f,0x00,sizeof f);
	memset(fir,0x00,sizeof fir); fir[0]=1;
	memset(C,0x00,sizeof C); C[M]=1;
	long long nowlen=1; int now=0; f[0][1<<N]=1;
	int LI=0; while ((1ll<<LI)<=m) LI++;
	for (int t=LI-1;t>=0;t--){
		int ne=now^1; long long *F=f[now]; long long *G=f[ne];
		memset(f[ne],0x00,sizeof f[ne]);
		long long lim=Lim[t];
		if ((m&(1ll<<t))==0){
			for (int i=0;i<(1<<N+1);i++) G[go[0][i]]+=F[i];
			for (int i=0;i<(1<<N+1);i++) G[go[1][i]]+=F[i];
			nowlen<<=1;
			bitset<150>x,y;
			x=0; y=0;
			for (int i=0;i<=M;i++) x[i<<1]=C[i];
			int del=max(0ll,nowlen-lim);
			for (int i=0;i<del;i++){
				int num=0;
			 	for (int j=0;j<=N;j++)
			 		num+=(x[(M<<1)-i-N+j+1]<<j);
			 	G[num]--;
			}
		//	cout<<M<<" "<<del<<endl;
			for (int i=0;i<=M;i++) 
				C[i]=x[i+M-del+1];
			nowlen=min(nowlen,lim);
			x=0;
			for (int i=0;i<=M;i++) x[i<<1]=fir[i];
			for (int i=0;i<=M;i++) fir[i]=x[i];
		} else {
			for (int i=0;i<(1<<N+1);i++) G[go[2][i]]+=F[i];
			for (int i=0;i<(1<<N+1);i++) G[go[3][i]]+=F[i];
			nowlen=(nowlen<<1)+n;
			bitset<150>x,y;
			x=0; y=0;
			for (int i=0;i<=M;i++) x[i<<1]=C[i];
			for (int i=0;i<=n;i++) if (A[i]) y^=(x<<i);
			for (int i=0;i<n;i++){
				int num=0;
				for (int j=0;j<=N;j++)
					num+=(y[(M<<1)+n-i-N+j+1]<<j);
				G[num]++;
			}
			int del=max(0ll,nowlen-lim);// cerr<<del<<endl;
			for (int i=0;i<del;i++){
				int num=0;
				for (int j=0;j<=N;j++)
					num+=(y[(M<<1)+n-i-N+j+1]<<j);
				G[num]--;
			}
			for (int i=0;i<=M;i++) C[i]=y[i+n+M-del+1];
			nowlen=min(nowlen,lim);
			x=0; y=0;
			for (int i=0;i<=M;i++) x[i<<1]=fir[i];
			for (int i=0;i<=n;i++) if (A[i]) y^=(x<<i);
			for (int i=0;i<=M;i++) fir[i]=y[i];
		}
		now=ne;
	}
	long long ans=0;
	for (int i=0;i<(1<<N+1);i++)
		if (pd[i]&&f[now][i]){
		//	cout<<"asd "<<f[now][i]<<" ";
		//	for (int j=0;j<=N;j++) if (i&(1<<j)) putchar('1'); else putchar('0'); putchar('\n');
			ans+=f[now][i];
		}
	return ans; 	
}
void solve(int t){
	checkB=0;
	scanf("%d%lld%d%lld%lld",&n,&m,&K,&L,&R); preK=K;
	memset(A,0x00,sizeof A);
	memset(B,0x00,sizeof B);
	scanf("%s",ch);
	for (int i=0;i<=n;i++) A[n-i]=ch[i]-'0';
	scanf("%s",ch);
	if (R-L+1<K){
		printf("0\n"); return;
	}
	for (int i=0;i<K;i++) B[i]=ch[i]-'0';
	zerobit=(N-preK+1<<1); //cout<<zerobit<<endl;
	for (int i=0;i<preK;i++) if (B[i]) checkB|=(1ll<<(N-i<<1));
	long long tot=n*m+1;
	for (int i=0;i<(1<<N+1);i++) preget(i);
	printf("%lld\n",solve(m,tot-L+1)-solve(m,tot-R+K-1));
}
int main(){
	//freopen("poly.in","r",stdin);
	//freopen("poly.out","w",stdout);
	int t; scanf("%d",&t);
	for (;t;t--) solve(t);
	return 0;
}