inlineintread(){ int x = 0, f = 0; char c = 0; while (!isdigit(c)) f |= c == '-', c = getchar(); while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); return f ? -x : x; }
#define N 14 #define int long long
int n, m, a[N][N], lst; int res;
unordered_map<int, int> f, g;
inlineintget(int st, int x){ return ((st >> (x - 1 << 1)) & 3); } inlinevoidchg(int &st, int x, int v){ st ^= (st >> (x - 1 << 1) & 3) << (x - 1 << 1); st ^= v << (x - 1 << 1); } inlineintfid(int st, int x, int s = 0){ if (get(st, x) == 1) { for (x ++; s != 1; x ++) { int t = st >> (x - 1 << 1) & 3; if (t == 1) s --; if (t == 2) s ++; } return x - 1; } else { for (x --; s != 1; x --) { int t = st >> (x - 1 << 1) & 3; if (t == 1) s ++; if (t == 2) s --; } return x + 1; } }
signedmain(){ for (int T = read(); T --;) { memset(a, 0, sizeof a), f.clear(), g.clear(), res = 0; n = read(), m = read(); int op = 0; for (int i = 1; i <= n; i ++) { for (int j = 1; j <= m; j ++) { a[i][j] = read(); op |= a[i][j]; } } if (!op) { puts("1"); continue; }
lst = n * m; for (int i = 1; i <= n; i ++) { for (int j = 1; j <= m; j ++) { if (a[i][j]) lst = i * (m - 1) + j; } } f[0] = 1; for (int i = 1; i <= n; i ++) { for (int j = 1; j <= m; j ++) { for (auto k : f) { int st = k.first, val = k.second; int l = get(st, j), u = get(st, j + 1); int r = a[i][j + 1], d = a[i + 1][j];
if (a[i][j] == 0) { if (l == 0 && u == 0) g[st] += val; continue; } if (l == 0 && u == 0) { chg(st, j, 1), chg(st, j + 1, 2), g[st] += val; } if (l == 0 && u != 0) { if (r) g[st] += val; if (d) chg(st, j, u), chg(st, j + 1, 0), g[st] += val; } if (l != 0 && u == 0) { if (d) g[st] += val; if (r) chg(st, j + 1, l), chg(st, j, 0), g[st] += val; } if (l == 2 && u == 1) { chg(st, j, 0), chg(st, j + 1, 0), g[st] += val; } if (l == 1 && u == 1) { int t = fid(st, j + 1); chg(st, j, 0), chg(st, j + 1, 0), chg(st, t, 1), g[st] += val; } if (l == 2 && u == 2) { int t = fid(st, j); chg(st, j, 0), chg(st, j + 1, 0), chg(st, t, 2), g[st] += val; } if (l == 1 && u == 2) { chg(st, j, 0), chg(st, j + 1, 0); if (i * (m - 1) + j == lst && st == 0) res += val; elseif (i * (m - 1) + j != lst) g[st] += val; continue; } } f.swap(g), g.clear(); } for (auto k : f) { if (k.first < (1 << (m << 1))) g[k.first << 2] = k.second; } f.swap(g), g.clear(); }