题目描述

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

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

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

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

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

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

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

对于一个串 $S$，$|S|$ 表示的是该串的长度。

对于一个串 $S$，我们定义串 $T$ 是它的前缀，当且仅当 $|T| \leq |S|$，且对于任意整数 $i$ 满足 $1 \leq i \leq |T|$，都有 $T$ 的左起第 $i$ 个字符与 $S$ 的左起第 $i$ 个字符相同。（形象地理解，即 $T$ 在 $S$ 的前部出现）

如：abc 是 abcdefg 的前缀，aba 不为 abba 的前缀，z 为 z 的前缀，空串为任意一个串的前缀。

---

输入格式

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

一行一个仅由小写字母组成的非空字符串 $S$。

---

输出格式

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

从小到大输出 $|R|$ 的所有不超过 $|S|$ 的可能值，所有值之间用单个空格隔开。

---

样例

输入

4
abcdcb
qwqwq
qaqaqqq
carnation

输出

4 6
2 3 4 5
6 7
9

---

数据范围与提示

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

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

---