# include <bits/stdc++.h>
using namespace std;

# ifndef ONLINE_JUDGE
# include "debug.h"
# else
# define debug(...) 0721
# define ps 0721
# endif

using i32 = signed;
using i64 = long long;

const int mod = 1e9 + 7;

int power(int a,int n) {
    int res = 1;
    while(n) {
        if(n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

vector<vector<int>> res(10,vector<int> (10));
void solve() {
    int n,m;
    cin >> n >> m;

    vector<vector<int>> a(n + 1,vector<int>(m + 1, 0));
    vector<vector<int>> b(n + 1,vector<int>(4,0));
    auto check = [&] (int x,int y,int val) -> bool {
        a[x][y] = val;
        if(b[x][0] <=3  && b[x][1] <= 3 && b[x][2] <= 3) {
            for (int i = 1; i < x; i++) {
                for (int j = 1; j < y; j++) {
                    
                    if(a[i][j] == a[i][y] && a[x][y] == a[x][j]) {
                        return false;
                    }
                    if(a[i][j] == a[x][j] && a[i][y] == a[x][y]) {
                        return false;
                    }
                } 
            }
            return true;
        }

        return false;
    };
    int ans = 0;

    auto dfs = [&] (auto self,int x,int y) -> void {
        if(x > n) {
            ans++;
            return;
        }
        if(y > m) {
            self(self,x + 1,1);
            return;
        }
        for (int i = 1; i <=3 ; i++) {
            b[x][i]++;
            if(check(x,y,i)) {
                self(self,x,y + 1);
            }
            b[x][i]--;
        }
    };
    if(n == 1 || m == 1) {
        cout << 0 << '\n';
        return;
    }
    if(n > 7 || n > 7) {
        cout << power(3,n * m) << '\n';
    }
    if(res[n][m] != -1) {
        cout << res[n][m] << '\n';
    }
    else {
         dfs(dfs,1,1);
        res[n][m] = power(3, n * m) - ans;
        res[n][m] = (res[n][m] + mod) % mod;
        cout << res[n][m] << '\n';
    }

}

i32 main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

# ifndef ONLINE_JUDGE
    freopen("Input.txt", "r", stdin);
    freopen("Output.txt", "w", stdout);
    freopen("Error.txt", "w", stderr);
# endif

    for (int i = 1; i < 9;i++) {
        for (int j = 1; j < 9;j++) {
            res[i][j] = -1;
        }
    }
    i32 t = 1;
    cin >> t;
    while (t --) {
        solve();
    }
    return 0;
}