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 $ 。

Aquamoon has a Rubik's Square which can be seen as an $ n \times n $ matrix, the elements of the matrix constitute a permutation of numbers $ 1, \ldots, n^2 $ . Aquamoon can perform two operations on the matrix: - Row shift, i.e. shift an entire row of the matrix several positions (at least $ 1 $ and at most $ n-1 $ ) to the right. The elements that come out of the right border of the matrix are moved to the beginning of the row. For example, shifting a row $ \begin{pmatrix} a & b & c \end{pmatrix} $ by $ 2 $ positions would result in $ \begin{pmatrix} b & c & a \end{pmatrix} $ ; - Column shift, i.e. shift an entire column of the matrix several positions (at least $ 1 $ and at most $ n-1 $ ) downwards. The elements that come out of the lower border of the matrix are moved to the beginning of the column. For example, shifting a column $ \begin{pmatrix} a \\ b \\ c \end{pmatrix} $ by $ 2 $ positions would result in $ \begin{pmatrix} b\\c\\a \end{pmatrix} $ . The rows are numbered from $ 1 $ to $ n $ from top to bottom, the columns are numbered from $ 1 $ to $ n $ from left to right. The cell at the intersection of the $ x $ -th row and the $ y $ -th column is denoted as $ (x, y) $ . Aquamoon can perform several (possibly, zero) operations, but she has to obey the following restrictions: - each row and each column can be shifted at most once; - each integer of the matrix can be moved at most twice; - the offsets of any two integers moved twice cannot be the same. Formally, if integers $ a $ and $ b $ have been moved twice, assuming $ a $ has changed its position from $ (x_1,y_1) $ to $ (x_2,y_2) $ , and $ b $ has changed its position from $ (x_3,y_3) $ to $ (x_4,y_4) $ , then $ x_2-x_1 \not\equiv x_4-x_3 \pmod{n} $ or $ y_2-y_1 \not\equiv y_4-y_3 \pmod{n} $ . Aquamoon wonders in how many ways she can transform the Rubik's Square from the given initial state to a given target state. Two ways are considered different if the sequences of applied operations are different. Since the answer can be very large, print the result modulo $ 998\,244\,353 $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 2\cdot 10^4 $ ). The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 3\le n \le 500 $ ). The $ i $ -th of the following $ n $ lines contains $ n $ integers $ a_{i1}, \ldots, a_{in} $ , representing the $ i $ -th row of the initial matrix ( $ 1 \le a_{ij} \le n^2 $ ). The $ i $ -th of the following $ n $ lines contains $ n $ integers $ b_{i1}, \ldots, b_{in} $ , representing the $ i $ -th row of the target matrix ( $ 1 \le b_{ij} \le n^2 $ ). It is guaranteed that both the elements of the initial matrix and the elements of the target matrix constitute a permutation of numbers $ 1, \ldots, n^2 $ . It is guaranteed that the sum of $ n^2 $ over all test cases does not exceed $ 250\,000 $ .

For each test case, if it is possible to convert the initial state to the target state respecting all the restrictions, output one integer — the number of ways to do so, modulo $ 998\,244\,353 $ . If there is no solution, print a single integer $ 0 $ .

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
0
0
4

In the first test case, the only way to transform the initial matrix to the target one is to shift the second row by $ 1 $ position to the right, and then shift the first column by $ 1 $ position downwards. In the second test case, it can be shown that there is no correct way to transform the matrix, thus, the answer is $ 0 $ .