在月色轻敲窗棂的夜里，徐老师翻开了一本古旧的魔法书。书页上只有两种符号：P 与 T。传说，当且仅当某段连续文字中 P 的数量与 T 的数量相等时，那一段就会化作“魔法咒语”，在掌心会出现许许多多金币。

请你帮徐老师，从每本魔法书的文字里，找出最长的魔法句子（即最长的连续子串，其中 P 与 T 的出现次数相同），并告诉他这段文字的长度。

输入格式

• 第一行一个整数 $t$ ，表示测试数据组数。
• 接下来 $t$ 行，每行给出一个仅由 P 和 T 组成的字符串，表示一本魔法书的文字。

输出格式

• 对于每组数据，输出一个非负整数，表示书中**最长魔法句子（连续子串）**的长度。

样例

2
PTPPTP
TPTTTTTPTPT

4
4

样例解释（助读）

• 对于 PTPPTP，例如子串 TPPT（位置 2〜5）中 P 与 T 各 2 个，长度为 4；不存在长度更长且平衡的连续子串。
• 对于 TPTTTTTPTPT，例如子串 PTTTTP（中段）同样可达到长度 4。

数据范围

• SubtTsk#0 $30分$：字符串长度 $\le 10^2$
• SubtTsk#1 $40分$：字符串长度 $\le 10^3$
• SubtTsk#2 $30分$：字符串长度 $\le 10^5$

对所有数据，$0 < t \le 10$。