P17183 [ICPC 2017 Hong Kong R] Equivalence of Sudoku

A Sudoku solution is one $9 \times 9$ matrix in which each digit from $1$ to $9$ occurs only once every row, every column and every $3 \times 3$ square. Given one Sudoku solution, $S$, it is easy to generate many other equivalent solutions, by performing one or more of the elementary transformations: $R$ for a rotation by $90, 180$ or $270$ degrees, $M$ for a mirror image by flipping along the horizontal or vertical axis, $B$ for a bijective substitution of each of the digits $1$ to $9$ being mapped to another set of digits $1$ to $9$. It can be seen that $S_1, S_2$, and $S_3$ are all equivalent to $S$ in the following example. :::align{center}  ::: A partial Sudoku is one in which not all of the 81 cells are filled up. We say that a partial Sudoku P1 is subsumed by (less than) another one P2 if there exists P which is equivalent to P2, and P is obtained from P1 by filling in one or more cells. In the following example, P1 is subsumed by P2 with respect to P, where P can be obtained from P2 via a bijective mapping $\{1,2,3,4,5,6,7,8,9\} \to \{2,9,3,7,8,6,1,5,4\}$, after rotating P2 clockwise by 90 degrees. Similarly, we say that P2 subsumes P1 or P2 is greater than P1 with respect to P. Note that it is not necessary that one of the matrices is completely filled. :::align{center}  ::: To summarize, between every two Sudoku matrices $S_1$ and $S_2$, there are four possible relationships: $S_1$ is equivalent to $S_2$ ($E$), $S_1$ is less than $S_2$ ($L$), $S_1$ is greater than $S_2$ ($G$), $S_1$ is incomparable to $S_2$ ($I$). Write a program to read in a list of $n$ Sudoku matrices and determine the pairwise relationship between them. The output is an $n \times n$ matrix showing the relationships $(E, L, G, I)$. It is obvious that the diagonal elements are all $E$ (every matrix is equivalent to itself trivially).

The first line contains the number of matrices $n$. Each subsequent set of $9$ lines corresponds to a (partial) Sudoku matrix. An unfilled cell is represented as $0$ (instead of blank). Assume that $2 < n \le 400$, all inputs are correct and all matrices are correct (partial) Sudoku matrices.

For each pair of input matrices, determine the relationship between them and output that relationship as a single letter $O \in \{E, L, G, I\}$, one line for each input matrix.