题目背景

绿绿和 Yazid 是好朋友。他们在一起做串串游戏。

题目描述

绿绿有一个由小写字母组成的非空字符串 $R$ ，但 Yazid 不知道它具体是什么。

我们定义翻转的操作：把一个串以最后一个字符作对称轴进行翻转复制。形式化地描述就是，如果他翻转的串为 $R$ ，那么他会将前 $\left| R\right|-1$ 个字符倒序排列后，插入到串的最后。

举例而言，串abcd进行翻转操作后，将得到abcdcba；串qw连续进行 $2$ 次翻转操作后，将得到qwqwq；串z无论进行多少次翻转操作，都不会被改变。

贪玩的绿绿进行了若干次（可能为 $0$ 次）翻转操作。

淘气的绿绿又展示出了一个非空串 $S$ ，并表示 $S$ 是最终的串 $R$ 的前缀。现在，他想考考 Yazid，初始的串 $R$ 的长度可能是多少。

Yazid 找到了正在参加清华校赛的你，请你来帮他解决这个问题。但聪明的 Yazid 发现，所有超过 $\left| S\right|$ 的整数都一定是 $R$ 的可能长度，因此你只需要告诉他不超过的 $\left| S\right|$ 的 $R$ 的可能长度即可。

为了帮助你理解问题，Yazid 还将对一些概念和记号做出解释：

对于一个串 $S$ ， $\left| S\right|$ 表示的是该串的长度。
对于一个串 $S$ $S$ ，我们定义串 $T$ $T$ 是它的前缀，当且仅当 $\left| T\right|\leq\left| S\right|$ $∣ T ∣ \leq ∣ S ∣$ ，且对于任意整数 $i$ $i$ 满足 $1\leq i\leq\left| T\right|$ $1 \leq i \leq ∣ T ∣$ ，都有 $T$ $T$ 的左起第 $i$ $i$ 个字符与 $S$ $S$ 的左起第 $i$ $i$ 个字符相同。（形象地理解，即 $T$ $T$ 在 $S$ $S$ 的前部出现）
- 如：abc是abcdefg的前缀，aba不为abba的前缀，z为z的前缀，空串为任意一个串的前缀。

输入包含多组数据，第一行一个整数 $T$ 表示数据组数。接下来依次描述每组数据，对于每组数据：

对于每组数据，输出 $1$ 行：

4
abcdcb
qwqwq
qaqaqqq
carnation

保证 $\left| S\right|\leq 10^6$ ， $\sum\left| S\right|\leq 5\times 10^6$ 。

$\sum\left| S\right|$ 表示的是单个测试点中所有数据 $\left| S\right|$ 的总和。