#include<bits/stdc++.h>
using namespace std;
#define ri int
typedef long long ll;
const int maxn=1e5+10;
template<class T>inline bool ckmin(T &x,const T &y){return x>y?x=y,1:0;}
template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,1:0;}
template<class T>inline void clear(T *arr,int siz,int val=0){memset(arr,val,sizeof(T)*(siz+1));}
bool ans[1<<25],cur[1<<25],vis[1<<25];
int m,n,sum[6][6]={{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,5,18,73,267},{0,0,18,150,1533,11398},{0,0,73,1533,31828,469972},{0,0,267,11398,469972,12785753}};
inline int idx(int x,int y){return x*m+y;}
bool dfs(int S){
	if(cur[S])return true;
	if(vis[S])return ans[S];
	cur[S]=vis[S]=true;
	ri T=0;
	for(ri i=0;i<n;++i)
		for(ri j=0;j<m;++j){
			ri cnt=0;
			for(ri k:{-1,0,1})
				for(ri l:{-1,0,1})
					if(k||l){
						ri mx=i+k,my=j+l;
						if(mx>=0&&mx<n&&my>=0&&my<m&&(S&(1<<idx(mx,my))))
							if(++cnt>3)
								goto skip;
					}
			if(S&(1<<idx(i,j))){
				if(cnt==2||cnt==3)T|=(1<<idx(i,j));
			}
			else{
				if(cnt==3)T|=(1<<idx(i,j));
			}
			skip:;
		}
	ans[S]=dfs(T),cur[S]=false;
	return ans[S];
}
int main(){
//	for(n=1;n<=5;++n)
//		for(m=1;m<=5;++m){
//			memset(ans,0,1<<(n*m));
//			memset(vis,0,1<<(n*m));
//			vis[0]=true;
//			for(ri i=0;i<(1<<(n*m));++i){
//				if(!vis[i])dfs(i);
//				sum[n][m]+=ans[i];
//			}
//		}
//	for(ri i=1;i<=5;++i,printf("\n"))
//		for(ri j=1;j<=5;++j)
//			printf("%d ",sum[i][j]);
	int t_case;
	scanf("%d",&t_case);
	while(t_case--){
		scanf("%d%d",&n,&m);
		printf("%d\n",sum[n][m]);
	}
	return 0;
}