Problem J: Tile Puzzle

You are visiting Ancient and Contemporary Museum. Today there is held an exhibition on the history of natural science. You have seen many interesting exhibits about ancient, medieval, and modern science and mathematics, and you are in a resting space now.

You have found a number of panels there. Each of them is equipped with N × N electric tiles arranged in a square grid. Each tile is lit in one of the following colors: black (unlit), red, green, yellow, blue, magenta, and cyan. Initially all the tiles are in black. When a tile is touched on, that tile and the eight adjacent tiles will change their colors as follows: black -> red, red -> green, green -> yellow, yellow -> blue, blue -> magenta, magenta -> cyan, and cyan -> black. Here, the leftmost and rightmost columns are considered adjacent, and so as the uppermost and lowermost rows. There is a goal pattern for each panel, and you are to change the colors of the tiles as presented in the goal pattern. For example, if you are given the goal pattern shown in the figure below for a panel of 4 × 4, you will touch on the upper-left tile once and then on the lower-right tile twice (note that this might not be the only way).

Since you are good at programming, you guess you can find the solution using your computer. So your job in this problem is to write a program for it.

Figure 1: Example Goal Pattern

Input

The input contains a series of datasets. Each dataset is given in the following format:

      N
      Row1
      ...
      RowN

N indicates the size (i.e. the number of rows and columns) of the electrical panel (3 ≤ N ≤ 15). Row_i describes the goal pattern of the i-th row and contains exactly N numbers separated by a space. The j-th number indicates the color of the j-th column, and it is one of the following: 0 (denoting black), 1 (red), 2 (green), 3 (yellow), 4 (blue), 5 (magenta), and 6 (cyan).

The input is terminated by a line containing a single zero. This line is not part of any datasets.

Output

For each dataset, your program should produce the output of N lines. The i-th line should correspond to the i-th row and contain exactly N numbers separated by a space, where the j-th number should be the number of touches on the tile of the j-th column. The number should be in the range from 0 to 6 inclusive.

If there is more than one solution, your program may output any of them. If it is impossible to make the goal pattern, your program should output a single line containing “-1” (without quotes) instead of the N lines.

A blank line should follow the output for every dataset (including the last one).

Sample Input

4
3 1 2 3
1 1 0 1
2 0 2 2
3 1 2 3
5
3 3 3 0 0
3 3 3 0 0
3 3 0 4 4
0 0 4 4 4
0 0 4 4 4
0

Output for the Sample Input

1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 2

0 0 0 0 0
0 3 0 0 0
0 0 0 0 0
0 0 0 4 0
0 0 0 0 0

---