310647: CF1864G. Magic Square

G. Magic Squaretime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

ExampleInput

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

Output

1
0
0
4

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

题目大意：
Aquamoon有一个魔方阵，可以表示为\( n \times n \)的矩阵，矩阵的元素构成数字1, ..., \( n^2 \)的排列。

Aquamoon可以在矩阵上执行两种操作：
1. 行移位，即将矩阵的一行向右移动若干位置（至少1，最多\( n-1 \)）。移出矩阵右侧边界的元素会移到该行的开始位置。
2. 列移位，即将矩阵的一列向下移动若干位置（至少1，最多\( n-1 \)）。移出矩阵下侧边界的元素会移到该列的开始位置。

行从上到下编号为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 \)行，每行包含\( n \)个整数，代表初始矩阵的每一行（\( 1 \le a_{ij} \le n^2 \)）。
- 再接下来的\( n \)行，每行包含\( n \)个整数，代表目标矩阵的每一行（\( 1 \le b_{ij} \le n^2 \)）。

输出：
- 对于每个测试用例，如果可以在遵守所有限制的情况下将初始状态转换为目题目大意： Aquamoon有一个魔方阵，可以表示为\( n \times n \)的矩阵，矩阵的元素构成数字1, ..., \( n^2 \)的排列。 Aquamoon可以在矩阵上执行两种操作： 1. 行移位，即将矩阵的一行向右移动若干位置（至少1，最多\( n-1 \)）。移出矩阵右侧边界的元素会移到该行的开始位置。 2. 列移位，即将矩阵的一列向下移动若干位置（至少1，最多\( n-1 \)）。移出矩阵下侧边界的元素会移到该列的开始位置。 行从上到下编号为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 \)行，每行包含\( n \)个整数，代表初始矩阵的每一行（\( 1 \le a_{ij} \le n^2 \)）。 - 再接下来的\( n \)行，每行包含\( n \)个整数，代表目标矩阵的每一行（\( 1 \le b_{ij} \le n^2 \)）。 输出： - 对于每个测试用例，如果可以在遵守所有限制的情况下将初始状态转换为目