Magic Square

2000ms

262144K

Description:

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

Input:

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

Output:

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

Sample Input:

Sample Output:

Note:

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

Informação

Provedor Codeforces

Código CF1864G