题目描述

龙骑士有一个由小写字母组成的非空字符串$\red{R，}$但我们暂时不知道它是什么。

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

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

龙骑士进行了若干次（可能为$\red{0}$次）翻转操作。

于此同时，龙骑士又展示出了一个非空串$\red{S，}$并表示$\red{S}$是最终的串$\red{R}$的前缀。现在，他想考考你 们，初始的串$\red{R}$的长度可能是多少。

不难发现，所有超过$\red{|S|}$的整数都一定是$\red{R}$的可能长度，因此你只需要告诉他不超过的$\red{|S|}$的$\red{R}$的 可能长度即可。

龙骑士是一个善良的人，为了帮助你理解问题，他对一些概念和记号做出解释：

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

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

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

输入格式

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

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

输出格式

对于每组数据，输出$\red{1}$行：

从小到大输出$\red{|R|}$的所有不超过$\red{|S|}$的可能值，所有值之间用单个空格隔开。 题目保证$\red{|S|<=10^6,\sum_{}^{}{|S|}<=5 \times 10^6}$。 $\red{\sum_{}^{}{|S|}}$表示的是单个测试点中所有数据$\red{|S|}$的总和。

样例

输入样例

4
abcdcb
qwqwq
qaqaqqq
carnation

输出样例

4 6
2 3 4 5
6 7
9