#include <bits/stdc++.h>

using namespace std;

const int P = 1e9 + 7;

int ksm(int y)
{
    int x = 3, res = 1;
    while (y) {
        if (y & 1) {
            res = 1ll * res * x % P;
        }
        x = 1ll * x * x % P;
        y >>= 1;
    }
    return res;
}

int n, m, a[25][25], res;

void dfs(int x, int y)
{
    int chk = 0;
    for (int i = 1; i <= n && !chk; ++i) {
        for (int k = 1; k <= m && !chk; ++k) {
            if (!a[i][k]) {
                continue;
            }
            for (int j = i + 1; j <= n; ++j) {
                for (int l = k + 1; l <= m; ++l) {
                    if (a[j][l]) {
                        chk |= ((a[i][k] == a[i][l]) && (a[j][k] == a[j][l]));
                        chk |= ((a[i][k] == a[j][k]) && (a[i][l] == a[j][l]));
                    }
                }
            }
        }
    }
    if (chk) {
        int ct = (n - x) * m + m - y + 1;
        ((res += ksm(ct)) >= P) && (res -= P);
        return;
    }
    if (x > n) {
//        for (int i = 1; i <= n; ++i) {
//            for (int j = 1; j <= m; ++j) {
//                printf("%d", a[i][j]);
//            }
//            puts("");
//        }
//        puts("");
        return;
    }
    for (int i = 1; i <= 3; ++i) {
        a[x][y] = i;
        if (y == m) {
            dfs(x + 1, 1);
        } else {
            dfs(x, y + 1);
        }
        a[x][y] = 0;
    }
    return;
}

signed main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        if (n > m) {
            swap(n, m);
        }
        if (n == 1) {
            puts("0");
            continue;
        }
        if (m >= 8) {
            printf("%d\n", ksm(n * m));
            continue;
        }
        if (n == 2 && m == 7) {
            puts("4767849");
            continue;
        }
        if (n >= 3 && m >= 7) {
            printf("%d\n", ksm(n * m));
            continue;
        }
        if (n == 3 && m == 5) {
            puts("14321907");
            continue;
        }
        if (n == 3 && m == 6) {
            puts("387406809");
            continue;
        }
        if (n == 3 && m == 7) {
            puts("460338013");
            continue;
        }
        if (n == 4 && m == 4) {
            puts("43022385");
            continue;
        }
        if (n == 4 && m == 5) {
            puts("486780060");
            continue;
        }
        if (n >= 4 && m >= 6) {
            printf("%d\n", ksm(n * m));
            continue;
        }
        if (n == 5 && m == 6) {
            puts("288599194");
            continue;
        }
        res = 0;
        dfs(1, 1);
        printf("%d\n", res);
    }
    return 0;
}