Description

$Gill$ 对字符串算法非常感兴趣。几天前，他学习了关于如何求一个串的最长回文子串的算法。你知道回文吗？回文就是一个非空串从左到右读和从右到左读是一样的串。例如，“ $madam$ ”和“ $x$ ”都是回文串，但是“ $xby$ ”不是。

$Gill$ 喜欢思考，所以今天他打算研究回文其它的一些性质。在一个串中， $Gill$ 可以找出很多对不相交的回文子串，他想知道在这些对中，哪一对的总长度最长。比如，在串“ $abacaefdfe$ ”中， (“ $a$ ”， ” $d$ ”)， (“ $aba$ ”， “ $e$ ”)， (“ $aba$ ”， ” $efdfe$ ”)都是合法对。但是(“ $aba$ ”， “ $aca$ ”)不是合法对，因为他们有重叠部分。对于这个例子，(“ $aba$ ”， ” $efdfe$ ”)和(“ $aca$ ”， ” $efdfe$ ”)这两个对都有最大总长度，最大总长度是 $3+5=8$ 。

Input Format

多组测试数据。在输入文件的第一行有一个整数 $T(1\le T \le 15)$ ，表示有 $T$ 组数据。 在接下来的 $T$ 行中，每一行给出一个串 $S$ 。 $(2\le |S|\le 100000,$ 只包含小写字母)

Output Format

对于每一个数据，在一行中输出答案。

2
abacaefdfe
abcdea

8
2