You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 2.0 seconds
Memory limit: 256.0 MB

# Problem
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 Format
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 Format
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$$$.

## Examples
```input
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$$$.

Now solve the problem and return the code.