让我听听你的声音吧，告诉我你旅途中的故事——

无论快乐的事，还是痛苦的事，还有那些铭刻在心的相遇。

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 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$ 仅包含小写英文字母。