Description

给定字符串S，计算next数组

Input

输入第一行是一个int型整数n, 表示后面有n行字符串.每行字符串长度小于10000个字符.

Output

输出n行, 每行为对应字符串的next数组.

Sample Input

2
ababcababex
dddabce

Sample Output

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