CF1864G.Magic Square

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

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$ 取模的值。

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

每个测试包含多个测试用例。第一行包含测试用例数量 $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$。

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

对于每个测试用例，如果可以在满足所有限制条件的前提下将初始状态转换为目标状态，则输出一个整数——即实现该转换的方案数，对 $998\,244\,353$ 取模。

若不存在可行解，则输出单个整数 $0$。

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

在第一个测试用例中，将初始矩阵变换为目标矩阵的唯一方法是：将第二行向右移动 $1$ 个位置，然后将第一列向下移动 $1$ 个位置。

在第二个测试用例中，可以证明不存在将矩阵正确变换的方法，因此答案为 $0$。