URI Online Judge | 2586

Cubenacci

By Ricardo Martins, IFSULDEMINAS BR Brazil

Timelimit: 1

One day, Rubiko, an accomplished Rubik's Cube player, wanted to come up with a different game using such a tool. He bought a colorless cube, separated the three layers, and put a number on each part of each layer, as in the example below.

Cubonacci

After that, based on the Fibonacci sequence, which each next number is formed by the sum of the two previous numbers, it created the sequence of Cubonacci, being, with each new iteration, the number of each part of each layer is updated with the Sum of the part itself and all the parts adjacent to it. Following the example above, the value where the number 1 is in the next iteration will become 60, which is the sum of 1 + 2 + 4 + 5 + 10 + 11 + 13 + 14.

Input

First, a value C is read, representing the number of test cases. In each test case, a value N (1 ≤ NXi (0 ≤ Xi ≤ 9), representing the values ​​of each part of each layer of the cube.

Output

For each test case, print the final 27 cube values ​​after all the iterations determined by the sequence, as in the example below.

Input Sample Output Sample

2
1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
2
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1

8 12 8
12 18 12
8 12 8
12 18 12
18 27 18
12 18 12
8 12 8
12 18 12
8 12 8
125 175 125
175 245 175
125 175 125
175 245 175
245 343 245
175 245 175
125 175 125
175 245 175
125 175 125