#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 2e3 + 10, mod = 1e9 + 7;

ll dp[20][20];
ll qmi(ll a, ll k)
{
    ll res = 1;
    while (k)
    {
        if (k & 1)res = res * a;
        k >>= 1;
        a = a * a;
    }
    return res;
}
int n, m, c[20][20];

bool check(int x, int y)
{
    for (int i = 1; i < x; i++)
    {
        for (int j = 1; j < y; j++)
        {
            if ((c[i][j] == c[i][y]) && (c[x][j] == c[x][y]))return 0;
            if ((c[i][j] == c[x][j]) && (c[i][y] == c[x][y]))return 0;
        }
    }
    return 1;
}

void dfs(int x, int y)
{
    if (y == m + 1) {
        y = 1, x++;
        if (x > n) {
            dp[n][m]++;
            return;
        }
    }
    for (int i = 0; i < 3; i++) {
        c[x][y] = i;
        if (check(x, y))dfs(x, y + 1);
    }
}

void solve()
{
    int n, m; cin >> n >> m;
    if (n > m)swap(n, m);
    if (m < 10)cout << dp[n][m] << '\n';
    else cout << qmi(3, n * m) << '\n';
}

int main()
{
    for (int i = 1; i < 10; i++)
    {
        for (int j = i; j < 10; j++)
        {
            n = i, m = j;
            if (i >= 4 && j >= 7)continue;
            dfs(1, 1);
            dp[i][j] = (qmi(3, i * j) - dp[i][j]) % mod;
        }
    }
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1; cin >> t;
    while (t--)solve();
    return 0;
}