Problem Description

如果一个字符串可以表示成 $SS^RS$ 的形式，那么称其是完美的。其中，$S^R$ 表示字符串 $S$ 翻转后的结果，具体来说，如果 $S$ 为 $S_1S_2\dots S_{|S|}$，那么 $S^R$ 为 $S_{|S|}S_{|S|-1}\dots S_1$（$|S|$ 表示字符串 $S$ 的长度）。

给定一个由小写字母组成的字符串 $L$，求 $L$ 的最长的完美子串的长度，如果 $L$ 没有完美子串，请输出 $0$。字符串 $S$ 是字符串 $T$ 的子串当且仅当存在两个整数 $i$ 和 $j$（$1\leq i\leq j\leq |T|$），使 $T_iT_{i+1}\dots T_j$ 和 $S$ 相同。

Input

测试点包含多组数据。第一行包含一个整数 $T$（$1\leq T\leq5$），表示数据组数。

每组数据包含一个由小写字母组成的字符串 $L$（$1\leq |L|\leq 2\times 10^5$）。

Output

每组数据包含一行，表示最长的完美子串的长度。如果没有完美子串，则输出 $0$。

5
abccbbc
aabbaab
abc
abcaacbbcaabbaab
aaaaaaaaa

6
6
0
9
9

Hint

样例共有五组数据：

第一组数据，最长的完美子串可以是 $bccbbc$，长度为 $6$。

第二组数据，最长的完美子串可以是 $abbaab$，长度为 $6$。

第三组数据，$s$ 没有完美子串，因此答案为 $0$。

第四组数据，最长的完美子串可以是 $bcaacbbca$，长度为 $9$。

第五组数据，最长的完美子串为 $s$ 本身，长度为 $9$。

可以证明，每组数据都不存在更长的完美子串。