《克鲁赛德战记》（Crusaders Quest）是一款有趣的手机游戏。一位神秘的女巫给游戏世界带来了巨大的黑暗，拯救女神以让她们释放力量来对抗女巫，是你王国唯一的希望。

为了拯救游戏世界，你需要选择三位英雄来争取胜利，并明智地使用他们的技能。屏幕底部会显示九个三种不同类型的技能块（每种类型三个）。如果 $k$ ($k \ge 1$) 个连续的块是相同类型的，你可以点击它们并将它们消除，从而触发它们所代表的强大技能。消除后，它们左侧的块会与右侧的块连接起来。此外，如果消除了 $k = 3$ 个相同类型的连续块，它们释放的强大技能将升级为超级技能，这是所有技能中最强大的。

DreamGrid 是这款游戏的新手，他想尽可能多地触发超级技能。给定满足上述描述的九个技能块，请帮助 DreamGrid 计算他能触发超级技能的最大次数。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$（约 50），表示测试用例的数量。每个测试用例：

第一行包含一个字符串 $s$ ($|s| = 9$)，由三个 'g'、三个 'a' 和三个 'o' 组成，代表九个三种不同类型的技能块。每种字符代表一种类型的技能块。

输出格式

对于每个测试用例，输出一个整数，表示 DreamGrid 能触发超级技能的最大次数。

样例

输入格式 1

7
gggaaaooo
aaoogggoa
googgaaao
agogaooag
goooggaaa
gogogoaaa
gaogaogao

输出格式 1

3
3
2
1
3
2
1

说明

对于第一个样例测试用例，DreamGrid 可以先消除 “aaa”（触发一次超级技能），从而将技能块变为 “gggooo”。然后他可以消除 “ggg”（触发另一次超级技能），最后消除 “ooo”（触发第三次超级技能）。因此答案是 3。

对于第二个样例测试用例，DreamGrid 可以先消除 “ggg”（触发一次超级技能），从而将技能块变为 “aaoooa”。然后他可以消除 “ooo”（触发另一次超级技能），最后消除 “aaa”（触发第三次超级技能）。因此答案也是 3。

对于第三个样例测试用例，DreamGrid 可以先消除 “aaa”（触发一次超级技能），从而将技能块变为 “googgo”。然后他可以消除 “oo” 得到 “gggo”，并消除 “ggg”（触发另一次超级技能）得到 “o”。因此答案是 2。很容易证明在这种技能块排列下，他无法触发三次超级技能。