爱丽丝（Alice）和鲍勃（Bob）正在玩一个游戏。爱丽丝拿了一张纸，上面有 $N \times M$ 个点，排成 $N$ 行 $M$ 列。

首先，爱丽丝用五种颜色 $c_0, c_1, c_2, c_3, c_4$ 中的一种对其中一些点进行染色。然后，鲍勃在具有公共边的相邻点之间画一些线段。

如果一个点的颜色是 $c_i$，则鲍勃连接该点的线段数量必须恰好为 $i$。否则，鲍勃可以连接任意数量的线段。

最后，爱丽丝会给其余未染色的点染色，规则相同：连接了 $i$ 条线段的点应该被染成颜色 $c_i$。

游戏结束后，爱丽丝可能会得到不同的颜色图案。假设初始染色的纸张总共可以产生 $K$ 种不同的图案，且对于第 $i$ 种图案，鲍勃有 $P_i$ 种画线的方法。爱丽丝想知道 $\sum_{i=1}^K P_i^2$ 的值。

输入格式

输入的第一行包含一个整数 $t$，表示测试用例的数量。接下来是 $t$ 个测试用例。

对于每个测试用例，第一行包含两个整数 $N$（$N \le 66$）和 $M$（$M \le 6$）。

接下来的 $N$ 行中，第 $i$ 行包含 $M$ 个整数，其中第 $j$ 个整数表示点 $(i, j)$ 的状态。如果该点被染成了颜色 $c_k$，则该整数为 $k$；否则为 $-1$。

输出格式

对于每个测试用例，输出 $\sum_{i=1}^K P_i^2 \bmod 10007$ 的值。

样例

输入样例 1

2
2 2
-1 -1
-1 -1
3 3
1 1 1
1 0 1
1 1 1

输出样例 1

18
4

说明

在第一组样例中，共有 15 种图案：

$$ \begin{matrix} \begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix} & \begin{bmatrix} 0 & 0 \\ 1 & 1 \end{bmatrix} & \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix} & \begin{bmatrix} 0 & 1 \\ 0 & 1 \end{bmatrix} & \begin{bmatrix} 1 & 0 \\ 1 & 0 \end{bmatrix} \end{matrix} $$

$$ \begin{matrix} \begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix} & \begin{bmatrix} 2 & 1 \\ 1 & 0 \end{bmatrix} & \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix} & \begin{bmatrix} 0 & 1 \\ 1 & 2 \end{bmatrix} & \begin{bmatrix} 2 & 2 \\ 2 & 2 \end{bmatrix} \end{matrix} $$

$$ \begin{matrix} \begin{bmatrix} 2 & 2 \\ 1 & 1 \end{bmatrix} & \begin{bmatrix} 1 & 1 \\ 2 & 2 \end{bmatrix} & \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix} & \begin{bmatrix} 1 & 2 \\ 2 & 1 \end{bmatrix} \end{matrix} $$

对于上述 14 种图案，每种都只有 1 种画线方案。

而对于以下图案：

$$ \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} $$

共有 2 种画线方案。因此答案为 $18 = 14 \times 1^2 + 1 \times 2^2$。