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

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

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