Description

《祖玛》曾是一款火爆全网的益智游戏。游戏的主角是一只祖玛青蛙，祖玛青蛙会吐出各种颜色的珠子，珠子造型美丽，并且有着神秘的色彩。环绕着祖玛青蛙的是载着珠子的轨道，随着时间增加各种颜色的珠子在队尾会不断增多，导致整个珠子队列不断向终点的洞口轨道逼近，祖玛青蛙必需遏止珠子滚进去，珠子一旦进入洞口游戏就失败了。

祖玛口中会出现随机颜色的珠子，玩家可以控制祖玛青蛙朝某个位置喷射珠子。吐出的珠子会撞进轨道上珠子的队列中，如果连续3个及以上珠子颜色相同即可以实现消除。消除后队列前方的珠子会倒退回来填补消除珠子位置的空缺。如果此时倒退末端的珠子和原有的最前端的珠子颜色一致且个数大于等于3个，则又会触发消除。只要满足条件，消除可以不断触发。

告诉你轨道上每个珠子的颜色，并且当前祖玛青蛙口中的珠子是可以变成任何颜色，请问发射这颗珠子最多可以消掉多少颗珠子。

Input Format

第一行一个正整数n（n≤10），表示当前有n组数据。

接下来n行，每行一个只包含大写字母且长度为l的字符串，每个字母代表一种颜色。

Output Format

输出n个正整数，每组数据输出最多可以消掉多少颗珠子。

1
AAACCCBBBAABBABCCCDA

15

Hint

【样例解释】

打一个B珠子到第12或13或14位置（第一个字母位置为1），出现了BBBB满足3个及以上同色珠子相连的条件，触发消除。消除后两端相连形成AAA再消除，AAA消除后BBBB相连再消除，BBBB消除后CCCCCC相连再消除，之后由于左边是AAA右边是D无法再消除。总共消除15颗。

【数据范围约定】

对于50%的数据，1≤l≤1000；
对于100%的数据，1≤l≤100000；