#include <bits/stdc++.h>
#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;
}
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 val[10][10];
int main(){
    for(n=2;n<=7;n++) for(m=n;m<=7;m++){
        if(n==2||n==3) ans=0,dfs(1,1),val[n][m]=ans;
        else if(n==4){
            if(m>6) val[n][m]=0;
            else ans=0,dfs(1,1),val[n][m]=ans;
        }
        else if(n==5){
            if(m>5) val[n][m]=0;
            else ans=0,dfs(1,1),val[n][m]=ans;
        }
    }
    int _;cin>>_;
    while(_--){
        cin>>n>>m;
        ans=0;
        if(n>m)swap(n,m);
        int tot=qmi(3,n*m);
        if(n==1) cout<<0<<'\n';
        else if(m>7) cout<<tot<<'\n';
        else cout<<(tot-val[n][m]+P)%P<<'\n';
    }
    return 0;
}