#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/16/problems/D

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

Diagonal Shuffle - Repovive Premier Round 6 | Repovive | 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

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

16D. Diagonal Shuffle

Constraints

Input

Output

Samples

16D. Diagonal Shuffle

Constraints

Input

Output

Samples