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

#ifdef LOCAL
#include "C:\Program Files\DEBUG\debug.h"
#else
#define debug(...) 114514
#define ps 114514
#endif

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(100, vector<int>(100));
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 > 9 || m > 9) {
        cout << power(3, n * m) << '\n';
    }
    if (res[n][m] != -1) {
        cout << res[n][m] << '\n';
    } else {
        ans = 0;
        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';
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int t = 1;
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            res[i][j] = -1;
        }
    }
    cin >> t;
    while (t--)
        solve();
    return 0;
}