题目描述

对于字符串 $W$，定义 $W^R$ 为 $W$ 反序后的字符串。先给定字符串 $S$，求 $S$ 的最大子串能表示成 $WW^RWW^R$ 的形式。

输入格式

第一行一个整数 $T$ 表示数据组数。

接下来 $T$ 行每行一个字符串 $S$。

输出格式

$T$ 行，每行一个整数表示答案。

2
abrahellehhelleh
rachelhellabracadabra

12
0

数据范围

对于 $100\%$ 的数据，保证 $T\leq 35$，$S$ 的长度小于等于 $3\times 10^5$。