施放法术是应对现实生活最难被理解的技术。事实上，人们很难区分真正的咒语（例如在战斗中使用并在法师大学中教授的 "abrahellehhelleh"）和尖叫声（例如没有受过教育的女巫用来对猫大喊大叫的 "rachelhellabracadabra"）。

最终，在“无闻大学”（Unheard University）进行的研究表明了人们如何衡量一个词（无论是真正的咒语还是尖叫声）的力量。结果表明，这与法师倒着念单词的能力有关。（实际上，一些歌手因为完全相同的能力而被烧死在火刑柱上，因为这被视为恶魔附身。）具体来说，一个词的力量是形如 $ww^Rww^R$ 的最大子串的长度（其中 $w$ 是任意字符序列，$w^R$ 是 $w$ 的反转）。如果不存在这样的子串，则该词的力量为 $0$。例如，"abrahellehhelleh" 的力量为 $12$，因为它包含 "hellehhelleh"；而 "rachelhellabracadabra" 的力量为 $0$。注意，一个词的力量总是 $4$ 的倍数。

输入格式

输入包含多组测试数据。

输入的第一行包含一个正整数 $Z \le 40$，表示测试数据的组数。

接下来有 $Z$ 组测试数据。每组测试数据占一行，包含一个长度最多为 $3 \cdot 10^5$ 的单词，由大写或小写英文字母组成。

输出格式

对于每组测试数据，输出一个整数 $k$，表示该单词的力量。

样例

输入样例 1

2
abrahellehhelleh
rachelhellabracadabra

输出样例 1

12
0