Iuli

It is the first day of school and you are in Computer Science class. Your best friend Iuli has a new challenge for you.

He hands you a string consisting of lowercase english characters and asks you to find the length of all its periods.

A period of a string is a prefix of it which has the property that the string can be written as a concatenation of that prefix with itself for a finite number of times.

For example, the periods of $aaaaaa$ are $a, aa, aaa, aaaaaa$.

Due to the high ammount of input and output data, it is recommended to code in C++, use streams and the following instructions before reading the input for speedup:

ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);

Input data

On the first line there will be an integer $t \leq 20$, the number of testcases.

On each of the next $t$ lines there will be a string $s$, $|s|\leq10^6$ containing lowercase letters of the english alphabet.

The sum of lengths of all strings in the input will not exceed $2\cdot10^7$.

Output data

The output will consist of $t$ lines.

On line $i$ there will be a list of integers signifying the periods of the $i^{th}$ string in the input. The numbers on each line will be sorted increasingly and will have a single space between them.

Constraints and clarifications

• For $30$ points, it is guaranteed that the sum of lengths of all strings in the input will not exceed $10^4$
• For another $40$ points, it is guaranteed that the sum of lengths of all strings in the input will not exceed $5\cdot10^6$
• For the last $30$ points, the sum of lengths of all strings in the input will not exceed $2\cdot10^7$.

Example

stdin

1
aaaaaa

stdout

1 2 3 6

Explanation

The periods of $aaaaaa$ are $a, aa, aaa, aaaaaa$ which have lengths $1, 2, 3, 6$.