squirrel

Time limit: 1s Memory limit: 1024MB Input: Output:

Task

A squirrel discovered a deposit of peanuts. The deposit has a weirder shape, as it is made of 33 rows of rooms, each of them having 33 rooms. The deposit has in total 99 rooms situated on the 3×33 \times 3 grid. We know the number of peanuts present in each of the 99 rooms from the matrix.

As the squirrel doesn’t like to see too many peanuts in a room or too few peanuts in another room, it will proceed as follows: from day 11, the squirrel will take all the rooms in which a maximal number of peanuts exists and moves exactly one peanut to every adjacent room.

The squirrel is now asking you the following question:

"How many peanuts will there be in each room after nn days?"

We need to answer to tt such questions the squirrel will give to us.

Input

The first line of the input contains tt, representing the number of tests we will need to solve (1t1001 \leq t \leq 100).

Each testcase will contain 44 lines.
The first line of the test will contain nn (1n10181 \leq n \leq 10^{18}), the number of days corresponding to each step.
The following 33 lines of the test will contain the grid, each of the lines having 33 columns, representing the initial values of the matrix (10aij101810 \leq a_{ij} \leq 10^{18}).
For tests worth 1414 points, (1n1001 \leq n \leq 100, 10ai,j1 00010 \leq a_{i,j} \leq 1 \ 000).
For tests worth 77 more points, (1n1051 \leq n \leq 10^5).
For tests worth 55 more points, (10ai,j1510 \leq a_{i,j} \leq 15).
For tests worth 1414 more points, (10ai,j10410 \leq a_{i,j} \leq 10^4).

Output

Each test will have the 3×33 \times 3 grid corresponding to the answer for that particular test case.

Example

stdin

4
2
15 14 18
16 15 13
11 18 14
3
11 14 13
13 12 15
14 16 12
4
16 12 14
13 14 12
11 14 12
1
11 12 13
14 13 11
12 13 11

stdout

16 17 14
14 13 16
13 16 15
13 13 13
12 13 15
15 13 13
12 14 14
14 14 11
13 12 14
12 12 13
11 14 11
13 13 11

Log in or sign up to be able to send submissions!