#include <bits/stdc++.h>
#define debug cerr << "\33[32m[" << __LINE__ << "]\33[m "
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int MOD = 1e9 + 7;
int n,m,ans,a[10][10];
void dfs(int x,int y){
    if(x>n){
        ans++;
        return;
    }
    F(i,1,3){
        a[x][y]=i;
        bool fl=1;
        F(p,1,x-1){
            F(q,1,y-1){
                if((a[p][q]==a[p][y]&&a[x][q]==a[x][y])||
                (a[p][q]==a[x][q]&&a[p][y]==a[x][y]))
                fl=0;
            }
            if(!fl) break;
        }
        if(fl){
            if(y==m) dfs(x+1,1);
            else dfs(x,y+1);
        }
    }
}
const int P=1e9+7;
int qmi(int x,int y){
    int res=1;for(;y;y>>=1){ if(y&1) res=1ll*res*x%P;x=1ll*x*x%P;}
    return res;
}
int query(int n, int m) {
	ans=0;
	::n = n, ::m = m;
			if(n>m)swap(n,m);
			int tot=qmi(3,n*m);
			if(n==1) return 0;
			else if(m>7){
				return tot;
			}
			else if(n==2||n==3){
				if(m>7) return tot;
				else{
					dfs(1,1);
					return (tot - ans + MOD) % MOD;
				}
			}
			else if(n==4){
				if(m>6) return tot;
				else{
					dfs(1,1);
					return (tot - ans + MOD) % MOD;
				}
			}
			else if(n==5){
				if(m>5) return tot;
				else{
					dfs(1,1);
					return (tot - ans + MOD) % MOD;
				}
			}
			else return tot;
}
int aa[10][10];
int main(){
    // freopen("1.out","w",stdout);
    // n=6,m=6;
    // dfs(1,1);
    // cout<<ans<<'\n';
    // exit(0);
	F(n, 1, 7)
		F(m, n, 7) {
			aa[n][m] = query(n, m);
		}
	int _; cin >> _;
	while (_--) {
		int n, m;
		cin >> n >> m;
		if (n >= m) swap(n, m);
		if (m > 7) {
			cout << qmi(3,n*m) << '\n';
		} else {
			// debug << qmi(3, n*m) << " " << aa[n][m] << endl;
			cout << aa[n][m] << '\n';
		}
	}
    return 0;
}