TetraVex is an edge-matching puzzle. The player is presented with a grid (by default, 3×3) and nine square tiles, each with four numbers one number on each edge. The objective of the game is to place the tiles in the grid in the proper position as fast as possible without rotating any tile. Two tiles can only be placed next to each other if the numbers on adjacent faces match.

In this problem you should print the final configuration.

Input

Input will start with 0 < t <= 100 (number of test cases).  Each test case describes the initial grid configuration in 9 lines; each line contains 4 integers in this order top, right, bottom, and left. These integers will be in range 0 to 9 inclusive.

Output

You should print one line for each test case containing a permutation of the numbers from 1 to 9 a1a2a3a4…a9 the digit ai should be the tile number in the input that should be put at the cell number i in the output configuration describing the final board configuration row-major order. If there are multiple solutions print the smallest lexicographically. There will always be a solution.

Example

Input:
1
6513
7908
7709
4671
1177
5217
1556
9045
8510

Output:
189547236