Problem Description

You are asking to write a solver for the skycrapers puzzle. The following is the rule for this puzzle:

Place a number from 1 to $n$ (integers only) into each cell so that each number appears exactly once in each row and column. ($n$ is the number of cells in each row.) Each number represents a skyscraper of its respective height. The numbers outside the grid indicate how many skyscrapers can be seen in the respective row or column from the respective direction; smaller skyscrapers are hidden behind higher ones. In other words, a skyscraper is visible if numbers of all skyscrapers in front of it are slower.

Input

The first line contains an integer $T (1\leq T\leq 100)$ - the number of test cases.

For each test cases, the first line contain an interger $n (4\leq n\leq 8)$. There are $n$ integers in each of the following $4$ lines, indicating the clues on the top, bottom, left and right side (from left to right or top to bottom).

It' guarantees that every puzzle has a unique solution.

All puzzles in the inputs are from [puzsq](https://puzsq.jp/main/index.php?puzzle=59) and [puzzlinkdb](https://puzz.link/db/?type=skyscrapers)
. So if you get TLE, you can try to solve these puzzles locally by your program, or even by hand. However, there is no precomputed thing in the model solution.

Output

For each test, output $n$ lines with $n$ numbers in each line.

2
5
0 0 0 5 0
0 4 2 0 0
0 0 4 3 0
3 3 0 0 0
6
0 4 0 0 3 0
0 0 4 0 0 0
0 3 0 4 0 5
0 4 0 3 0 0

4 5 3 1 2
5 4 1 2 3
1 2 4 3 5
2 3 5 4 1
3 1 2 5 4
6 1 4 2 3 5
1 2 6 5 4 3
4 5 3 1 6 2
3 4 5 6 2 1
5 6 2 3 1 4
2 3 1 4 5 6