Given an nxn matrix, if it satisfy the next constraints it could be called a "Magic Square".

Constraints:

* The sum of the n rows, n columns and the two main diagonals of the matrix must be equal to the same number m, called magic constant
* the n² positions of the matrix must contains natural numbers between 1 to n², with no repetitions.

Input

Each test case consist in a natural number n (0 < n <= 20) denoting the matrix dimension. Then, the next n² natural numbers will represent the values that initially contains the matrix.
For each position a_ij (1 <= i,j <= n) of the matrix, we have:  0 <= a_ij <= n², for all ij.
A value of 0 in an initial position aij of the matrix means that you must find a number to complete that place. A non-zero value means that you cannot change that value for the given position.

Output

For each case you must print the case number (starting from 1).
Then, in the next n lines you must print the magic square if exists or the phrase ''No Solution'' (without the quotes) if doesn't exist a solution for the given initial configuration.

See the output example.

If for a given initial configuration exists more than one solution, you should give the lower one assuming a lexicographic order. For lexicographic comparison you should consider lines in first place.

Print a blank line between test cases.

For example:
2 7 6    
9 5 1    
4 3 8    

it's lexicographically before than:

4 3 8
9 5 1
2 7 6

Example

Input:
3
8 0 0
0 0 0
0 0 0

2
1 1
0 0



Output:


Case #1
8 1 6 
3 5 7 
4 9 2 

Case #2
No Solution