畀我聽吓你嘅聲音啦，同我講吓你旅途入面嘅故事——
無論係開心嘅事，定係痛苦嘅事，仲有嗰啲銘記喺心嘅相遇。
題目描述
畀定一個長度為 $n$ 嘅字串 $S$，下標由 $1$ 開始。記 $S(i, j)=S_iS_{i+1}\cdots S_j$，表示 $S$ 由第 $i$ 個字元到第 $j$ 個字元組成嘅子字串。
如果非空字串 $B$ 同時係字串 $X$ 嘅前綴同後綴，而且 $|B|<|X|$，就稱 $B$ 係 $X$ 嘅一個 Border，當中 $|X|$ 表示字串 $X$ 嘅長度。
一開始，你喺子字串 $S(1, n)$。每次跳躍都按以下方式進行：
- 喺目前身處嘅子字串入面揀一個子字串 $X$。
- 揀 $X$ 嘅一個 Border $B$，要求 $2|B|\ge |X|$。
- 跳去 $B$ 喺 $X$ 入面作為前綴或者後綴所對應嘅子字串，兩者任揀其一。
例如，當 $S$ 係 aabaaba，你喺 $S(1, 7)$ 嗰陣，可以揀 $X=S(2, 7)=$ abaaba。佢嘅 Border 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 嘅限制條件。
數據範圍
呢題有啟用合理嘅子任務依賴。
| 子任務 | $n\le$ | $\sum n\le$ | 特殊性質 | 分數 |
|---|---|---|---|---|
| $1$ | $18$ | $500$ | 無 | $5$ |
| $2$ | $500$ | $14$ | ||
| $3$ | $5\times 10^3$ | $5\times 10^3$ | $21$ | |
| $4$ | $10^5$ | $10^5$ | $18$ | |
| $5$ | $2\times 10^5$ | $2\times 10^5$ | A | $15$ |
| $6$ | B | $13$ | ||
| $7$ | C | $2$ | ||
| $8$ | 無 | $12$ |
特殊性質 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$ 只包含小寫英文字母。