Diagonal Shuffle - Repovive Premier Round 6 | Repovive

16D. Diagonal Shuffle

2000 pts2s256 MB

You are given an $n \times n$ grid $a$ . Each integer from $1$ to $n^2$ appears exactly once in the grid.

The sorted grid is the grid where $a_{i,j}=(i-1)n+j$ for every $1 \le i,j \le n$ .

You may apply the following operation any number of times:

Choose two integers $i$ and $j$ such that $1 \le i < n$ and $1 \le j < n$ . Then, inside the $2 \times 2$ subgrid with top-left cell $(i,j)$ , simultaneously do both swaps:

swap $a_{i,j}$ with $a_{i+1,j+1}$ ;
swap $a_{i+1,j}$ with $a_{i,j+1}$ .

For each test case, determine whether it is possible to transform the given grid into the sorted grid.

Constraints

$1 \le t \le 100$
$1 \le n \le 500$
The sum of $n$ over all test cases is at most $500$ .
In each test case, every integer from $1$ to $n^2$ appears exactly once.

Input

t

\left. \begin{array}{l} n \\ a_{1,1}\quad a_{1,2}\quad \cdots\quad a_{1,n} \\ a_{2,1}\quad a_{2,2}\quad \cdots\quad a_{2,n} \\ \vdots \\ a_{n,1}\quad a_{n,2}\quad \cdots\quad a_{n,n} \end{array} \right\} \times t

Output

\left. \begin{array}{l} \text{Yes or No} \end{array} \right\} \times t

Samples

Input

Case 1

1
1

Case 2

2
1 2
3 4

Case 3

2
4 2
3 1

Case 4

Case 5

Explanation

Case 1

The grid is already sorted.

Case 2

The grid is already sorted, so no operation is needed.

Case 3

For a 2 by 2 grid, the only operation swaps both diagonals at the same time. This grid swaps only one diagonal compared to the sorted grid, so it cannot be sorted.

Case 4

It can be sorted by applying operations with top-left cells (1,1), (2,2), (1,1), and (2,2).

Case 5

The values 1 and 2 are placed on cells with different parity from where they must end up, and the operation cannot change this parity for a value.

Output

Case 1

Yes

Case 2

Yes

Case 3

No

Case 4

Yes

Case 5

No

You are given an $n \times n$ grid $a$ . Each integer from $1$ to $n^2$ appears exactly once in the grid.

The sorted grid is the grid where $a_{i,j}=(i-1)n+j$ for every $1 \le i,j \le n$ .

You may apply the following operation any number of times:

Choose two integers $i$ and $j$ such that $1 \le i < n$ and $1 \le j < n$ . Then, inside the $2 \times 2$ subgrid with top-left cell $(i,j)$ , simultaneously do both swaps:

swap $a_{i,j}$ with $a_{i+1,j+1}$ ;
swap $a_{i+1,j}$ with $a_{i,j+1}$ .

For each test case, determine whether it is possible to transform the given grid into the sorted grid.

$1 \le t \le 100$
$1 \le n \le 500$
The sum of $n$ over all test cases is at most $500$ .
In each test case, every integer from $1$ to $n^2$ appears exactly once.

t

\left. \begin{array}{l} n \\ a_{1,1}\quad a_{1,2}\quad \cdots\quad a_{1,n} \\ a_{2,1}\quad a_{2,2}\quad \cdots\quad a_{2,n} \\ \vdots \\ a_{n,1}\quad a_{n,2}\quad \cdots\quad a_{n,n} \end{array} \right\} \times t

\left. \begin{array}{l} \text{Yes or No} \end{array} \right\} \times t

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

16D. Diagonal Shuffle

Constraints

Input

Output

Samples

16D. Diagonal Shuffle

Constraints

Input

Output

Samples