Sumdoku

Sumdoku is a variant of Sudoku. As in Sudoku, you fill a $9 \times 9$ grid with the digits 1 through 9 so that each digit occurs exactly once in every row, exactly once in every column, and exactly once in each of the nine $3 \times 3$ sub-squares. Sudoku fixes the value of certain cells. Sumdoku instead constrains the sum of two adjacent cells inside the same $3 \times 3$ sub-square.

A symbol placed between two cells means the sum of the two values on either side of it is less than 10 for <, equal to 10 for =, and greater than 10 for >. For a horizontal pair the two values are the left one and the right one, and for a vertical pair they are the one above and the one below. A constraint is given only for a pair of adjacent cells inside the same sub-square, never for a pair that crosses a sub-square border.

The picture below shows how the symbols sit in the grid.

Write a program that fills the grid from the constraints.

The first line contains $P$, the number of data sets ($1 \le P \le 500$). The data sets are independent and are processed identically.

Each data set consists of 16 lines. The first line holds the data set number $K$, and $K$ runs from 1 to $P$ in order. The next 15 lines consist of the characters <, = and >.

Lines 1, 3, 5, 6, 8, 10, 11, 13 and 15 hold 6 characters each. They give the constraints on horizontally adjacent cells for grid rows 1 through 9 in that order. The 6 characters of one line are the constraints for the column pairs (1, 2), (2, 3), (4, 5), (5, 6), (7, 8), (8, 9).

Lines 2, 4, 7, 9, 12 and 14 hold 9 characters each. They give the constraints on vertically adjacent cells for the row pairs (1, 2), (2, 3), (4, 5), (5, 6), (7, 8), (8, 9) in that order. The 9 characters of one line are the constraints for columns 1 through 9.

Every data set has at least one grid that satisfies all of its constraints.

Print 10 lines for each data set. The first line is the data set number $K$. The next 9 lines are the rows of the grid. The $j$th number on the $i$th of those 9 lines is the value in column $j$ of row $i$, and the nine numbers on a line are separated by a single space.

If more than one grid satisfies the constraints, print the lexicographically smallest one, reading the 81 values in row-major order starting at row 1, column 1.