#include<iostream>
#include<cstdio>
using namespace std;
const int N=7;
int n,m,vis[N][N],_vis[N][N],vq[40002021];
int dx[]={0,0,1,-1,1,1,-1,-1},dy[]={1,-1,0,0,-1,1,-1,1};
int read(){
	int x=0,f=1; char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int get(int x,int y){
	return (x-1)*m+y;
}
void solveit(){
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			int res=0;
			for(int k=0;k<8;k++){
				int ri=i+dx[k],rj=j+dy[k];
				if(ri<1 || ri>n || rj<1 || rj>m)continue;
//				cout<<i<<" "<<j<<" "<<ri<<" "<<rj<<endl;
				if(vis[ri][rj])++res;
			}
			if(vis[i][j]){
				if(res==2 || res==3)_vis[i][j]=1;
				else _vis[i][j]=0;
			}
			else{
				if(res==3)_vis[i][j]=1;
				else _vis[i][j]=0;
			}
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			vis[i][j]=_vis[i][j];
}
int getval(){
	int w=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			w|=(vis[i][j]<<(get(i,j)-1));
//			w=w<<1|vis[i][j];
	return w;
}
int main()
{
	int aq=read();
	while(aq--){
		n=read(); m=read();
		if((n==4 && m==5) || (n==5 && m==4)){puts("469972");continue;}
		else if(n==5 && m==5){puts("12785753");continue;}
		else if(n==4 && m==4){puts("31828");continue;}
		int S=(1<<(n*m)),T=0,ans=0;
		for(int i=0;i<S;i++)vq[i]=0;
		for(int i=0;i<S;i++){
//			if(!(i%100000))cout<<i<<endl;
			for(int j=1;j<=n;j++)
				for(int k=1;k<=m;k++){
					if((1<<(get(j,k)-1))&i)vis[j][k]=1;
					else vis[j][k]=0;
				}
			++T;
			int fl=0;
			vq[getval()]=T;
			while(1){
				solveit();
				int w=getval();
				if(!w){fl=0;break;}
				if(vq[w]==T){fl=1;break;} vq[w]=T;
			}
			if(fl){
//				for(int j=1;j<=n;j++,cout<<endl)
//					for(int k=1;k<=n;k++)cout<<vis[j][k];
//				cout<<endl;
			}
			ans+=fl;
		}
		cout<<ans<<endl;
	}
	return 0;
}