Дай мені почути твій голос, розкажи мені історії зі своєї подорожі —

І радісні, і болісні, а також про ті зустрічі, що закарбувалися в серці.

Far Away Song - anemoi

Опис задачі

Дано рядок $S$ довжини $n$ з індексацією від $1$. Позначимо через $S(i, j)=S_iS_{i+1}\cdots S_j$ підрядок $S$, що складається із символів від $i$-го до $j$-го включно.

Якщо непорожній рядок $B$ є одночасно префіксом і суфіксом рядка $X$, причому $|B|<|X|$, то $B$ називають бордером рядка $X$, де $|X|$ позначає довжину рядка $X$.

Спочатку ви перебуваєте в підрядку $S(1, n)$. Кожен стрибок виконується так:

1. Виберіть підрядок $X$ усередині підрядка, в якому ви зараз перебуваєте.
2. Виберіть бордер $B$ рядка $X$, для якого $2|B|\ge |X|$.
3. Перестрибніть у підрядок, що відповідає входженню $B$ як префікса або суфікса $X$, обравши будь-який із цих двох варіантів.

Наприклад, якщо $S$ — це aabaaba і ви перебуваєте в $S(1, 7)$, можна вибрати $X=S(2, 7)=$ abaaba. Довжина його бордера aba дорівнює рівно половині $|X|$, тому ви можете перестрибнути в $S(2, 4)$ або $S(5, 7)$.

Для кожного $1\le i\le n$ окремо знайдіть максимальну кількість стрибків, які можна виконати, починаючи з $S(1, n)$ і зрештою діставшись $S(i, i)$. Якщо дістатися неможливо, відповідь дорівнює $-1$. Дозволяється не виконувати жодного стрибка.

Вхідні дані містять кілька наборів тестових даних.

Вхідні дані

Перший рядок містить ціле число $T$ — кількість наборів тестових даних.

Далі послідовно наведено набори тестових даних. Кожен набір займає один рядок, що містить рядок $S$.

Вихідні дані

Для кожного набору тестових даних виведіть один рядок із $n$ цілих чисел, де $i$-те число — відповідь для $S(i, i)$ (якщо дістатися $S(i, i)$ неможливо, виведіть -1).

Приклади

Вхідні дані 1

5
abbababbab
bbabbaabbabbaaabab
babbaaaaabaabaaabaaba
baabaabaabaacaabaabaabaacaabaabaabaac
bbaabaaaaabbbbbbbababaabaabaabbabababbbabbabbabbba

Вихідні дані 1

-1 2 2 -1 -1 -1 2 2 -1 -1
3 3 -1 3 3 2 2 3 3 -1 3 3 2 2 2 -1 -1 -1
-1 -1 1 1 4 4 4 4 4 -1 3 3 -1 3 3 3 -1 3 3 -1 -1
-1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1
1 1 2 2 -1 4 4 4 4 4 6 6 6 6 6 6 6 -1 -1 -1 -1 3 3 -1 3 3 -1 3 3 1 1 -1 -1 -1 -1 -1 2 3 3 -1 3 3 -1 3 3 -1 3 3 2 -1

Примітка

У першому наборі даних $S=$ abbababbab; його префікс і суфікс довжини $5$ обидва дорівнюють abbab. Можна виконати два стрибки одним із таких способів:

• Спочатку перестрибнути в $S(1, 5)$, потім вибрати $S(2, 3)=$ bb і перестрибнути в $S(2, 2)$ або $S(3, 3)$.
• Спочатку перестрибнути в $S(6, 10)$, потім вибрати $S(7, 8)=$ bb і перестрибнути в $S(7, 7)$ або $S(8, 8)$.

Продовжити стрибки можна лише тоді, коли перший стрибок веде до одного із зазначених двох входжень abbab, а наступний стрибок може привести лише до окремого символу. Тому для кожної з цих чотирьох позицій максимальна кількість стрибків дорівнює $2$.

До решти позицій дістатися стрибками неможливо, тому відповідь для них дорівнює $-1$.

Приклад 2

Див. wind2.in і wind2.ans у вкладеннях. Цей приклад задовольняє обмеження підзадачі 3.

Приклад 3

Див. wind3.in і wind3.ans у вкладеннях. Цей приклад задовольняє обмеження підзадачі 5.

Приклад 4

Див. wind4.in і wind4.ans у вкладеннях. Цей приклад задовольняє обмеження підзадачі 6.

Приклад 5

Див. wind5.in і wind5.ans у вкладеннях. Цей приклад задовольняє обмеження підзадачі 8.

Обмеження

У цій задачі ввімкнено логічно обґрунтовані залежності між підзадачами.

Спеціальна властивість A: існує непорожній рядок $P$, такий що $S$ є префіксом нескінченного періодичного рядка $P^{\infty}$, причому $|P|\le 10$.

Спеціальна властивість B: $S$ згенеровано випадково, тобто кожен символ $S$ вибрано рівномірно випадково з набору символів розміру $\ge 2$.

Спеціальна властивість C: для всіх $1\le i<n$ виконується $S_i\neq S_{i+1}$.

Для всіх даних гарантовано $1\le n\le 2\times 10^5$, а сума довжин рядків усіх наборів тестових даних в одному тестовому файлі задовольняє $\sum n\le 2\times 10^5$. Рядок $S$ містить лише малі англійські літери.