小 Z 给出了一些对于字符串的操作、概念和定义：

对于一个字符串 S，|S| 表示该串的长度。

对于一个字符串 S，我们定义一个字符串 T 是它的前缀，当且仅当 |T| < |S|，且对于任意整数 i\in[1,|T|] 都满足 T 的第 i 个字符等于 S 的第 i 个字符。形式化地说，T 在 S 的前面出现。

例如：abc 是 abcd 的前缀；a 是 a 的前缀；空串是任意一个串的前缀；abc 不是 abbc 的前缀。


字符串 S 的镜像操作：以 S 的最后一个字符串为中心做镜像翻转。

例如，abcd 执行镜像操作为 abcdcba；qw 执行 2 次镜像操作过程为 qw \rightarrow qwq \rightarrow qwqwq；z 无论进行多少次镜像操作都不会被改变。

现在有一个字符串 T，小 Z 对该字符串进行了若干次镜像操作（可能为 0 次）。现在，告诉你一个非空字符串 S，表示字符串 T 若干次镜像操作之后的最终字符串的前缀，小 Z 想知道，原始 字符串 T 的可能长度是多少。

显然，所有超过 |S| 长度的字符串都一定是 T 的可能长度，因此，小 Z 只想知道不超过 |S| 的 T 的可能长度。

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

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

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

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