Dice Grid
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Debora is playing a video game. In one of the levels, she is given a cube and a flat colorful $$$n \times n$$$ grid. The cell in row $$$i$$$ and column $$$j$$$ of the grid is denoted by $$$(i, j)$$$ and has color $$$c_{i, j}$$$. Debora can see the whole grid, including the color of each cell.

The cube face size matches the grid cell size. Whenever we say that the cube is located at cell $$$(i, j)$$$, it means that its bottom face coincides with the grid cell $$$(i, j)$$$. Opposite to the bottom face is the top face. The face that is "looking" at cell $$$(i + 1, j)$$$ is called the front face. The back face is "looking" at cell $$$(i - 1, j)$$$, the right face is "looking" at cell $$$(i, j + 1)$$$, and the left face is "looking" at cell $$$(i, j - 1)$$$.

Initially, the cube is located at cell $$$(1, 1)$$$. The goal of the game is to roll the cube to cell $$$(n, n)$$$.

From any cell $$$(i, j)$$$, Debora can only move the cube down — to cell $$$(i + 1, j)$$$, or right — to cell $$$(i, j + 1)$$$. The way to move the cube down is to rotate it around the edge connecting its bottom and front faces. For instance, after the rotation, the front face becomes the new bottom face. Similarly, the way to move the cube to the right is to rotate it around the edge connecting its bottom and right faces.

The faces of the cube are not colored yet. Debora has to paint each face in any color she wants. At every moment of the game, including the moments when the cube is located at $$$(1, 1)$$$ and $$$(n, n)$$$, the cube's bottom face color has to match the color of the grid cell where the cube is located.

The goal is to paint the cube in such a way that Debora will be able to move the cube from cell $$$(1, 1)$$$ to cell $$$(n, n)$$$ satisfying the conditions above. Find any possible cube coloring.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 625$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ — the number of rows and columns in the grid ($$$2 \le n \le 50$$$).

The $$$i$$$-th of the following $$$n$$$ lines contains $$$n$$$ integers $$$c_{i, 1}, c_{i, 2}, \ldots, c_{i, n}$$$ ($$$0 \le c_{i, j} < 2^{24}$$$). The RGB color of cell $$$(i, j)$$$ is $$$c_{i, j}$$$.

It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$2500$$$.

Output

For each test case, if no coloring exists, print a single word "No" on a separate line.

Otherwise, in the first line, print a single word "Yes".

In the second line, print six integers $$$a_b$$$, $$$a_l$$$, $$$a_k$$$, $$$a_f$$$, $$$a_r$$$, and $$$a_t$$$ — the colors of the bottom, left, back, front, right, and top faces of the cube, respectively, in its initial position at cell $$$(1, 1)$$$ ($$$0 \le a_i < 2^{24}$$$).

If several possible colorings exist, print any of them.

Example

Input

    421 10 031 2 39 6 47 8 141 2 3 49 8 7 510 8 12 213 14 15 641 2 3 45 6 7 89 10 11 1213 14 15 16

Output

    Yes
    1 3 4 0 0 5
    Yes
    1 10 10 4 2 3
    Yes
    1 4 6 5 2 3
    No

Note

In the third example test case, the cube can be moved from $$$(1, 1)$$$ to $$$(4, 4)$$$ with the following sequence of moves: right, right, right, down, down, and down.