Alice 和 Bob 经营着一家水果店，向世界各地的顾客配送美味的水果。他们的品牌主打四种来自台湾的招牌水果：番石榴 (guava)、荔枝 (lychee)、芒果 (mango) 和释迦 (sugar apple)。

他们开设了多家分店，每家分店都使用相同的布局来展示水果。每天，每家店的门面都会布置成一个 $4 \times 4$ 的网格。网格中展示的水果满足：每一行和每一列都恰好包含这四种不同水果中的每一种——即每行每列都没有重复的水果。

Generated by ChatGPT 4o

为了确保各分店的一致性，每天晚上，Alice 和 Bob 都会准备一个具有有效展示布局的 $4 \times 4$ 水果盒，并让员工在第二天早上将这些盒子送到各个分店。

Alice 和 Bob 有两个喜欢吃水果的孩子，Charlie 和 Dianne。一天晚上，他们偷偷溜进办公室，发现桌上放着准备好的水果盒。

Charlie 忍不住了——他拿了一个水果并吃掉了。“嗯……我希望我能尽可能多吃一些，同时又不会让明天的员工感到困惑，”他想。

Dianne 注意到了哥哥的恶作剧，自己也觉得饿了，于是也拿了另一个水果。很快，两人开始轮流从盒子里一次拿走一个水果。

他们的规则很简单：只有当拿走一个水果后，盒子里剩余的水果仍然能够唯一确定原本的 $4 \times 4$ 展示布局（即在保持每行每列水果不重复的规则下，只有一种方法可以补全整个布局）时，他们才能拿走这个水果。

Charlie 和 Dianne 都不想成为那个无法再拿水果的人。因此，他们都遵循相同的策略：

“如果存在一种方法，使我最终能够拿走最后一个水果而不违反规则，我就会选择拿走，并尽量最大化我能吃到的水果总数。但如果我的兄弟姐妹能够智胜我并拿走最后一个水果，我则会转而尝试最小化他们能拿走的水果数量。”

现在，给你水果盒的当前状态。也就是说，在上述规则下，已经有一些水果被拿走了。你的任务是编写一个程序，预测在两个孩子都采取最优策略进行游戏后，盒子里最终会剩下多少个水果。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$。接下来是每个测试用例的描述。

每个测试用例包含四行，其中第 $i$ 行包含一个长度为 $4$ 的字符串，表示水果盒布局的第 $i$ 行。每个字符都属于集合 $\{G, L, M, S, X\}$，分别代表四种水果之一，或者用 $X$ 表示空位。

输出格式

对于每个测试用例，请在每行输出对应的答案。

数据范围

• $1 \le t \le 10$
• 保证输入的每个水果盒都是有效的。也就是说，存在唯一的一种方法来填补空位，使得每行和每列的水果都互不相同。

样例

输入样例 1

2
GLMS
LSGM
MGXL
SMLG
GLMS
LMSG
MSXL
SGLM

输出样例 1

5
5