Description

众所周知，mahe不仅长得帅，还擅长使用魔法！ mahe获得了一个仅由A和B组成的字符串。他可以至多使用一次魔法来改变字符串。 魔法：选择一个连续子串，满足子串中 A 的数量等于B的数量且所选字典序不增(i+1位置的字符字典序小于等于i位置的字符字典序)，然后按字典序从小到大排序这个子串，即变成形如AAA...AAABBB...BBB这样的字符串(A和B的数量均与原来的子串相同)。 他想知道，在他至多使用一次魔法后，这个字符串能够出现的最长的字典序不递减的子串的长度为多少。

Format

Input

第一行包含一个整数T，代表样例数。(1<=T<=100) 接下来每行给出一个长度非空的字符串。字符串长度 1<=len<=5e5 题目保证每组数据字符串长度和不超过5e5

Output

输出T行 每组样例输出一行一个正整数表示答案。

Samples

1
AABBAA

6

Tips

选择”BBAA”的子串，这个子串 A 和 B 的出现次数相等且满足不上升。使用魔法变成AABB，则整个字符串变为AAAABB，所以最长不递减子串长度为6。