Description

给定一个字符串a=(a0,a1,a2,a3....an-1),计算其Failure Function.

Input

输入第1行有一个int型正整数T (T<100), 表示有T组输入.
后面接着T行字符串,每个字符串长度小于10000.

Output

对每一行字符串输出其Failure Function.

Sample Input

2
abcabcacab
km2d1km2d1

Sample Output

-1 -1 -1 0 1 2 3 -1 0 1
-1 -1 -1 -1 -1 0 1 2 3 4