Description

Lvlvl has a non-empty string $R$ consisting of lowercase letters, but Yazid does not know what it is.

We define the flip operation: flip-copy a string using its last character as the axis of symmetry. Formally, if the string to be flipped is $R$, then take the first $\left| R\right|-1$ characters, reverse them, and append them to the end of the string.

For example, after applying the flip operation to abcd, we get abcdcba; if we apply the flip operation $2$ times in a row to qw, we get qwqwq; for z, no matter how many times we apply the flip operation, it will not change.

The playful Lvlvl performed the flip operation several times (possibly $0$ times).

Then the naughty Lvlvl showed a non-empty string $S$, and said that $S$ is a prefix of the final string $R$. Now he wants to test Yazid: what lengths could the initial string $R$ have?

Yazid asked you, who are participating in the Tsinghua campus contest, to help solve this problem. But the clever Yazid noticed that every integer greater than $\left| S\right|$ must be a possible length of $R$, so you only need to tell him the possible lengths of $R$ that do not exceed $\left| S\right|$.

To help you understand the problem, Yazid also explains some concepts and notation:

• For a string $S$, $\left| S\right|$ denotes its length.
• For a string $S$, we say that a string $T$ is its prefix if and only if $\left| T\right|\leq\left| S\right|$, and for every integer $i$ with $1\leq i\leq\left| T\right|$, the $i$-th character of $T$ from the left is the same as the $i$-th character of $S$ from the left. (Intuitively, $T$ appears at the beginning of $S$.)
  • For example: abc is a prefix of abcdefg; aba is not a prefix of abba; z is a prefix of z; the empty string is a prefix of any string.

Input Format

The input contains multiple test cases. The first line contains an integer $T$ indicating the number of test cases. Each test case is described as follows:

• One line contains a non-empty string $S$ consisting only of lowercase letters.

Output Format

For each test case, output one line:

• Output all possible values of $\left| R\right|$ that do not exceed $\left| S\right|$, in increasing order, separated by a single space.

4
abcdcb
qwqwq
qaqaqqq
carnation

4 6
2 3 4 5
6 7
9

Hint

Constraints

It is guaranteed that $\left| S\right|\leq 10^6$ and $\sum\left| S\right|\leq 5\times 10^6$.

$\sum\left| S\right|$ denotes the total length $\left| S\right|$ of all test cases in a single test point.

Notes

• The input size is large, so please pay attention to input efficiency.
• What does the last string in the sample mean?

Copyright Information

From the 2018 Tsinghua University Programming Contest and Collegiate Invitational (THUPC2018). Thanks to Pony.ai for supporting this contest.

Resources such as the editorial can be found at https://github.com/wangyurzee7/THUPC2018.

Translated by ChatGPT 5