讓我聽聽你的聲音吧，告訴我你旅途中的故事——

無論快樂的事，還是痛苦的事，還有那些銘刻在心的相遇。

Far Away Song - anemoi

題目敘述

給定一個長度為 $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)$。每次跳躍按如下方式進行：

1. 在目前所在的子字串中選擇一個子字串 $X$。
2. 選擇 $X$ 的一個 Border $B$，要求 $2|B|\ge |X|$。
3. 跳到 $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 的約束條件。

資料範圍

本題開啟合理的子任務依賴。

特殊性質 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$ 僅包含小寫英文字母。