Hãy để tôi nghe giọng nói của bạn, hãy kể cho tôi những câu chuyện trên hành trình của bạn —

Dù là những chuyện vui, những chuyện đau buồn, hay cả những cuộc gặp gỡ khắc sâu trong tim.

Far Away Song - anemoi

Mô tả bài toán

Cho một xâu $S$ có độ dài $n$, được đánh chỉ số bắt đầu từ $1$. Ký hiệu $S(i, j)=S_iS_{i+1}\cdots S_j$ là xâu con của $S$ gồm các ký tự từ vị trí thứ $i$ đến vị trí thứ $j$.

Nếu xâu không rỗng $B$ vừa là tiền tố vừa là hậu tố của xâu $X$, và $|B|<|X|$, thì $B$ được gọi là một Border của $X$, trong đó $|X|$ biểu thị độ dài của xâu $X$.

Ban đầu, bạn đang ở xâu con $S(1, n)$. Mỗi bước nhảy được thực hiện như sau:

1. Chọn một xâu con $X$ trong xâu con mà bạn đang ở.
2. Chọn một Border $B$ của $X$, sao cho $2|B|\ge |X|$.
3. Nhảy đến xâu con tương ứng với $B$ khi nó là tiền tố hoặc hậu tố của $X$; bạn có thể chọn một trong hai.

Ví dụ, khi $S$ là aabaaba và bạn đang ở $S(1, 7)$, bạn có thể chọn $X=S(2, 7)=$ abaaba. Border aba của nó có độ dài đúng bằng một nửa $|X|$, vì vậy bạn có thể nhảy đến $S(2, 4)$ hoặc $S(5, 7)$.

Với mỗi $1\le i\le n$, hãy tìm riêng số bước nhảy tối đa có thể thực hiện khi xuất phát từ $S(1, n)$ và cuối cùng đến $S(i, i)$. Nếu không thể đến được, đáp án là $-1$. Bạn được phép không thực hiện bước nhảy nào.

Có nhiều bộ dữ liệu kiểm thử.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$, biểu thị số bộ dữ liệu kiểm thử.

Tiếp theo là lần lượt từng bộ dữ liệu kiểm thử. Mỗi bộ gồm một dòng biểu diễn xâu $S$.

Dữ liệu ra

Với mỗi bộ dữ liệu kiểm thử, in ra một dòng chứa $n$ số nguyên; số nguyên thứ $i$ là đáp án cho $S(i, i)$ (nếu không thể đến $S(i, i)$, hãy in ra -1).

Ví dụ

Dữ liệu vào 1

5
abbababbab
bbabbaabbabbaaabab
babbaaaaabaabaaabaaba
baabaabaabaacaabaabaabaacaabaabaabaac
bbaabaaaaabbbbbbbababaabaabaabbabababbbabbabbabbba

Dữ liệu ra 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

Ghi chú

Trong bộ dữ liệu đầu tiên, $S=$ abbababbab, tiền tố và hậu tố có độ dài $5$ của nó đều là abbab. Có thể thực hiện hai bước nhảy như sau:

• Trước tiên nhảy đến $S(1, 5)$, sau đó chọn $S(2, 3)=$ bb và nhảy đến $S(2, 2)$ hoặc $S(3, 3)$.
• Trước tiên nhảy đến $S(6, 10)$, sau đó chọn $S(7, 8)=$ bb và nhảy đến $S(7, 7)$ hoặc $S(8, 8)$.

Chỉ khi bước nhảy đầu tiên đến một trong hai xâu abbab nói trên thì mới có thể tiếp tục nhảy, và bước nhảy tiếp theo chỉ có thể đến một ký tự đơn lẻ. Vì vậy, số bước nhảy tối đa cho cả bốn vị trí này đều là $2$.

Không thể đến các vị trí còn lại bằng cách nhảy, nên đáp án là $-1$.

Ví dụ 2

Xem wind2.in và wind2.ans trong tệp đính kèm. Ví dụ này thỏa mãn các giới hạn của nhiệm vụ con 3.

Ví dụ 3

Xem wind3.in và wind3.ans trong tệp đính kèm. Ví dụ này thỏa mãn các giới hạn của nhiệm vụ con 5.

Ví dụ 4

Xem wind4.in và wind4.ans trong tệp đính kèm. Ví dụ này thỏa mãn các giới hạn của nhiệm vụ con 6.

Ví dụ 5

Xem wind5.in và wind5.ans trong tệp đính kèm. Ví dụ này thỏa mãn các giới hạn của nhiệm vụ con 8.

Giới hạn

Bài toán này áp dụng các quan hệ phụ thuộc hợp lý giữa các nhiệm vụ con.

Tính chất đặc biệt A: Tồn tại một xâu không rỗng $P$ sao cho $S$ là tiền tố của xâu lặp vô hạn $P^{\infty}$ và $|P|\le 10$.

Tính chất đặc biệt B: $S$ được sinh ngẫu nhiên, nghĩa là mỗi ký tự của $S$ được chọn ngẫu nhiên đều từ một tập ký tự có kích thước $\ge 2$.

Tính chất đặc biệt C: Với mọi $1\le i<n$, ta có $S_i\neq S_{i+1}$.

Với tất cả dữ liệu, đảm bảo $1\le n\le 2\times 10^5$, và tổng độ dài các xâu của mọi bộ dữ liệu kiểm thử trong một tệp kiểm thử là $\sum n\le 2\times 10^5$. Xâu $S$ chỉ chứa các chữ cái tiếng Anh viết thường.