#include <bits/stdc++.h>

using namespace std;

#define fr(i, x, y) for (int i = (x), _ed = (y); i <= _ed; i++) 
#define rp(i, x, y) for (int i = (x), _ed = (y); i >= _ed; i--) 

#define int long long

int T;
int n, m;

const int maxn = (1 << 20) + 45;

const int ax[8] = {0, 0, 1, -1, 1, -1 , -1, 1},
	  	  ay[8] = {1, -1, 0, 0, 1, -1, 1, -1};

int a[8][8], b[8][8];

int fa[maxn], size[maxn];
int find(int x) {
	if (fa[x] == x) return x;
	else return fa[x] = find(fa[x]);
}

void trans() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			b[i][j] = 0;
			int res = 0;
			for (int k = 0; k < 8; k++) {
				res = res + a[i + ax[k]][j + ay[k]];
			}
			if (a[i][j] == 1) {
				if (res == 2 || res == 3) 
					b[i][j] = 1;
			}
			else if (res == 3) b[i][j] = 1;
		}
	}
}
signed main() {
	int T;
	cin >> T;
	while (T--) {
		cin >> n >> m;
		if (n == 5 && m == 5) {
			printf("12785753\n"); continue;
		}
		if (n == 4 && m == 5) {
			printf("469972\n"); continue;
		}
		if (n == 5 && m == 4) {
			printf("469972\n"); continue;
		}
		for (int i = 0; i <= n + 1; i++) for (int j = 0; j <= m + 1; j++) a[i][j] = b[i][j] = 0;
		for (int i = 0; i < (1 << (n * m)); i++) {
			fa[i] = i; size[i] = 1;
		}
		for (int i = 0; i < (1 << (n * m)); i++) {
			for (int x = 1; x <= n; x++) {
				for (int y = 1; y <= m; y++) {
					int id = (x - 1) * m + y;
					if (i & (1 << (id - 1))) a[x][y] = 1;
					else a[x][y] = 0;
				}
			}
			int res = 0;
			trans();
			for (int x = 1; x <= n; x++) {
				for (int y = 1; y <= m; y++) {
					int id = (x - 1) * m + y;
					res = res + (1 << (id - 1)) * b[x][y];
				}
			}
			if (find(res) == find(i)) continue;
			size[find(res)] += size[find(i)];
			fa[find(i)] = find(res);
		}
		int ans = (1ll << (n * m));
		ans = ans - size[find(0)];
		cout << ans << endl;
	}
	return 0;
}