Intellectual Property

Erast Kopi is a well known designer of Sudoku puzzles. His puzzle collections sold so well that imitations and plagiarisms followed. Before he files a lawsuit, he wants to gather more evidence.

A Sudoku puzzle is a $9 \times 9$ table divided into $3 \times 3$ subtables of $3 \times 3$ cells each. A cell may hold one digit from 1 to 9. The goal of the puzzle is to fill the empty cells with digits so that every row, every column and each of the nine $3 \times 3$ subtables contains every digit from 1 to 9 exactly once.

Kopi keeps a database of Sudoku puzzles and wants to know whether it holds similar puzzles. Puzzle $P$ is similar to puzzle $Q$ if some sequence of the operations below turns $P$ into $Q$.

• pick two digits $x$ and $y$, then replace every $x$ with $y$ and every $y$ with $x$;
• swap two of the row triples $(1, 2, 3)$, $(4, 5, 6)$, $(7, 8, 9)$;
• swap two rows that belong to the same row triple;
• swap two of the column triples $(1, 2, 3)$, $(4, 5, 6)$, $(7, 8, 9)$;
• swap two columns that belong to the same column triple;
• flip along the diagonal that joins the top left corner to the bottom right corner. After this operation columns become rows and rows become columns.

Help Kopi find the similar puzzles in his database.

The first line contains one integer $n$, the number of puzzles in the database ($1 \le n \le 20$).

The rest of the input describes the puzzles $P_1, P_2, \dots, P_n$. Each puzzle takes nine lines of nine characters. Each character is either a digit from 1 to 9 or a dot . that marks an empty cell. One empty line separates consecutive puzzles.

The input has no spaces. The puzzles are not guaranteed to be solvable, so a row or a column may repeat a digit.

For every pair $(i, j)$ with $1 \le i < j \le n$, print Yes if puzzle $P_i$ is similar to puzzle $P_j$ and No otherwise, one answer per line.

The pairs come in the order $(1, 2), (1, 3), \dots, (1, n), (2, 3), (2, 4), \dots, (n - 1, n)$. That is, first compare $P_1$ against $P_2, P_3, \dots, P_n$ in this order, then compare $P_2$ against $P_3, P_4, \dots, P_n$, and so on.