Description

:::align{right}

Generated by ChatGPT 4o :::

Alice and Bob run a fruit business that delivers delicious fruits to customers around the world. Their brand showcases four iconic fruits from Taiwan: guava, lychee, mango, and sugar apple.

They’ve opened multiple branches, and each branch uses the same layout to display fruits. Each day, the storefront of every shop is arranged as a $4 \times 4$ grid. The grid displays fruits such that every row and every column contains exactly one of each of the four different fruits—no duplicates per row or column.

To ensure consistency across branches, every evening, Alice and Bob prepare a $4 \times 4$ fruit box with a valid display layout and have their employees deliver the boxes to each branch the next morning.

Alice and Bob have two children, Charlie and Dianne, who love eating fruit. One evening, they sneak into the office and find the prepared fruit boxes sitting on the table.

Charlie can’t resist—he grabs one fruit and eats it. “Mmm... I wish I could eat as many as possible without confusing the staff tomorrow,” he thinks.

Dianne, noticing her brother’s mischief and feeling hungry herself, takes another fruit. Soon, the two begin taking turns, each grabbing one fruit at a time from the box.

Their rule is simple: They can only take a fruit if, after removing it, the remaining fruits in the box still uniquely determine the original $4 \times 4$ display (i.e., there’s only one way to complete the display while preserving the distinct-fruit-per-row-and-column rule).

Neither Charlie nor Dianne wants to be the one who can’t grab a fruit anymore. So they both follow the same strategy:

“If there’s a way I can eventually grab the last fruit without violating the rule, I’ll take it, and I’ll try to maximize the total number of fruits I can eat. But if my sibling could outsmart me and grab the last fruit, I’ll instead try to minimize the number of fruits they can take.”

Now, you are given the current status of the fruit box. That is, some fruits are already taken under the rule. Your task is to write a program that predicts the total number of fruits that will remain in the box after both kids have played optimally.

Input Format

Each test contains multiple test cases. The first line contains the number of test cases $t$. The description of the test cases follows.

Each test case contains four lines, the $i$-th of which contains a string of length four, representing the $i$-th row of the layout of the fruit box. Each character will be in the set $\{\texttt{G}, \texttt{L}, \texttt{M}, \texttt{S}, \texttt{X}\}$, indicating each of the four fruits, or an empty slot denoted by $\texttt{X}$.

Output Format

For each test case, please output the specified answer in each line.

2
GLMS
LSGM
MGXL
SMLG
GLMS
LMSG
MSXL
SGLM

5
5

Hint

• $1 \le t \le 10$
• It is guaranteed that each input fruit box is valid. That is, there exists a unique way to fill in the empty slots such that each row and each column has distinct fruits.