CF1864G Magic Square

Aquamoon 有一个魔方，可以看作一个 $n \times n$ 矩阵，矩阵的元素构成数字的排列 $1, \ldots, n^2 $ 。 Aquamoon 可以对矩阵执行两种操作： - 行移位，即将矩阵的整行向右移动几个位置（至少 $ 1 $ 且最多 $ n-1 $ ）。 超出矩阵右边界的元素将移至行的开头。 例如，将行 $ \begin{pmatrix} a & b & c \end{pmatrix} $ 移动 $ 2 $ 位置将导致 $ \begin{pmatrix} b & c & a \end{pmatrix} $ ; - 列移位，即将矩阵的整列向下移动几个位置（至少 $ 1 $ 且最多 $ n-1 $ ）。 来自矩阵下边界的元素被移动到列的开头。 例如，将列 $ \begin{pmatrix} a \\ b \\ c \end{pmatrix} $ 移动 $ 2 $ 个位置将导致 $ \begin{pmatrix} b\\c\\a \end{pmatrix} $ . 行从上到下编号为$1$到$n$，列从左到右编号为$1$到$n$。 第 $ x $ 行和第 $ y $ 列交叉处的单元格表示为 $ (x, y) $ 。 Aquamoon 可以执行多项（可能是零）操作，但她必须遵守以下限制： - 每行、每列最多可以移动一次； - 矩阵的每个整数最多可以移动两次； - 任意两个整数移动两次后的偏移量不能相同。 形式上，如果整数 $ a $ 和 $ b $ 被移动了两次，假设 $ a $ 已将其位置从 $ (x_1,y_1) $ 更改为 $ (x_2,y_2) $ ，并且 $ b $ 已将其位置从 $ (x_3,y_3) $ 到 $ (x_4,y_4) $ ，然后 $ x_2-x_1 \not\equiv x_4-x_3 \pmod{n} $ 或 $ y_2-y_1 \not\equiv y_4-y_3 \pmod{n } $ . Aquamoon 想知道她可以通过多少种方式将魔方从给定的初始状态转变为给定的目标状态。 如果应用操作的顺序不同，则认为两种方式不同。 由于答案可能非常大，因此输出对 $ 998\,244\,353 $ 取模的结果。

每个测试包含多个测试用例。 第一行包含测试用例的数量 $ t $ ( $ 1 \le t \le 2\cdot 10^4 $ )。 测试用例的描述如下。 每个测试用例的第一行包含一个整数 $ n $ ( $ 3\le n \le 500 $ )。 接下来的 $ n $ 行的第 $ i $ 行包含 $ n $ 个整数 $ a_{i1}, \ldots, a_{in} $ ，表示初始矩阵的第 $ i $ 行 ( $ 1 \le a_{ij} \le n^2 $ )。 接下来的 $ n $ 行中的第 $ i $ 行包含 $ n $ 个整数 $ b_{i1}, \ldots, b_{in} $ ，表示目标矩阵的第 $ i $ 行( $ 1 \le b_{ij} \le n^2 $ )。 保证初始矩阵的元素和目标矩阵的元素都构成数字的排列 $ 1, \ldots, n^2 $ 。 保证所有测试用例的$n^2$总和不超过$250\,000$。

对于每个测试用例，如果可以在尊重所有限制的情况下将初始状态转换为目标状态，则输出一个整数 - 执行此操作的方法数，以 $ 998\,244\,353 $ 为模。 如果没有解决方案，则打印单个整数 $ 0 $ 。 ### 输入输出样例 #### 输入 #1 ```` 4 3 1 2 3 4 5 6 7 8 9 7 2 3 1 4 5 6 8 9 3 1 2 3 4 5 6 7 8 9 3 2 1 6 5 4 9 7 8 3 1 2 3 4 5 6 7 8 9 7 8 1 2 3 4 5 6 9 3 1 2 3 4 5 6 7 8 9 3 8 4 5 1 9 7 6 2 ```` #### 输出 #1 ```` 1 0 0 4 ````

在第一个测试用例中，将初始矩阵转换为目标矩阵的唯一方法是将第二行向右移动 $1$ 位置，然后将第一列向下移动 $1$ 位置。 在第二个测试用例中，可以表明没有正确的方法来变换矩阵，因此，答案是 $ 0 $ 。