#include<bits/stdc++.h>
#define ll long long
#define N 55
#define Q 100005
using namespace std;
vector<ll> opt[Q],has[N];
ll T,n,q,x,y,id[Q][2],tot,k,diff[Q],g[N<<1][Q],f[2][N<<1][Q];
bool vis[N][Q];
vector<ll> sta;
char s[N];
inline ll get_dif(vector<ll> x){
	ll ans1 = 0,ans2 = 0,p = 1;
	ll i=0,j=x.size()-1;
	while(i<=j){
		if(x[i]>x[j]){
			if(p&1) ans1+=x[i];
			else ans2+=x[i];
			i++;
		}
		else{
			if(p&1) ans1+=x[j];
			else ans2+=x[j];
			j--;
		}
		p^=1;
	}
	return ans1-ans2;
}
inline ll get_val(vector<ll> x){
	ll temp = 0;
	for(ll i=0;i<x.size();i++) temp=(temp*13331+x[i]+60)%1999997;
	return temp;
}
bool operator==(vector<ll> a,vector<ll> b){
	if(a.size()!=b.size()) return 0;
	for(ll i=0;i<a.size();i++) if(a[i]!=b[i]) return 0;
	return 1;
}
struct hsh_table{
	vector<ll> val[2000005];
	ll val2[2000005],ne[2000005],head[2000005],tot=0;
	void insert(vector<ll> x,ll y){
		ll p = get_val(x);
		tot++;
		ne[tot] = head[p],head[p] = tot,val[tot] = x,val2[tot] = y;
	}	
	ll found(vector<ll> x){
		ll p = get_val(x);
		for(ll i=head[p];i;i=ne[i]){
			if(val[i]==x) return val2[i];
		}
		return -1;
	}
}op;
inline ll dfs(ll step){
	ll now = op.found(sta);
	if(now!=-1&&vis[step-1][now]) return now;
	vector<ll> bf = sta;	
	if(now==-1) now = tot++,op.insert(bf,now),diff[now] = get_dif(bf);
//	if(step-1==2){
//		cout<<"! "<<now<<endl;
//		for(ll i=0;i<sta.size();i++) cout<<sta[i]<<" ";
//		cout<<endl;
//	}	
	vis[step-1][now] = 1,has[step-1].push_back(now);
	sta = bf;
	sta.push_back(1);
	while(sta.size()>=3&&sta[sta.size()-2]>=sta[sta.size()-3]&&sta[sta.size()-2]>=sta[sta.size()-1]){
		ll dif = sta[sta.size()-3]+sta[sta.size()-1]-sta[sta.size()-2];
		sta.pop_back(),sta.pop_back(),sta.pop_back(),sta.push_back(dif);
	}
//	if(now==82622&&step-1==2){
//		cout<<"&&& ";
//		for(ll i=0;i<sta.size();i++) cout<<sta[i]<<" ";
//		cout<<endl;
//	}
	if(step+1<=51) id[now][0] = dfs(step+1);
//	if(now==82622&&step-1==2){
//		cout<<"fuck id "<<id[now][0]<<endl;
//	}
	sta = bf;
	sta.push_back(2);
	while(sta.size()>=3&&sta[sta.size()-2]>=sta[sta.size()-3]&&sta[sta.size()-2]>=sta[sta.size()-1]){
		ll dif = sta[sta.size()-3]+sta[sta.size()-1]-sta[sta.size()-2];
		sta.pop_back(),sta.pop_back(),sta.pop_back(),sta.push_back(dif);
	}
	if(step+1<=51) id[now][1] = dfs(step+1);
	sta = bf;
	return now;
}
inline void init(){dfs(1);}
ll ans[N<<1][N<<1];
inline void solve(){
	memset(ans,0,sizeof(ans));
	cin>>n>>q>>(s+1);
	f[0][0][0] = 1;	
	for(ll i=0;i<n;i++){
		for(ll j=(i+1);j<=2*(i+1);j++) for(ll k=0;k<has[i+1].size();k++) f[(i+1)&1][j][has[i+1][k]]=0;
		for(ll j=i;j<=2*i;j++){
			for(ll k=0;k<has[i].size();k++){
				if(s[i+1]!='2') f[(i+1)&1][j+1][id[has[i][k]][0]]+=f[i&1][j][has[i][k]];
				if(s[i+1]!='1') f[(i+1)&1][j+2][id[has[i][k]][1]]+=f[i&1][j][has[i][k]];
			}
		}
	}
	for(ll i=n;i<=2*n;i++){
		for(ll j=0;j<has[n].size();j++){
			ll s1 = i,s2 = diff[has[n][j]];
			ll s3 = (s1+s2)/2,s4 = (s1-s2)/2;
			if(s3+s4==s1&&s3-s4==s2&&s3>=0&&s4>=0) ans[s3][s4] += f[n&1][i][has[n][j]];
		}
	}
//	cout<<"### "<<f[n&1][5][1]<<" "<<id[82622][0]<<" "<<id[3][1]<<endl;
	while(q--){
		cin>>x>>y;
		cout<<ans[x][y]<<endl;
	}
}
int main(){
	ios::sync_with_stdio(false);
	init();
	cin>>T;
	while(T--) solve();
	return 0;
}