J. Emordnilap
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Given a 1-indexed string $$$s$$$ of length $$$n$$$. For each $$$1\le i\le n$$$, a non-negative integer $$$r$$$ is called a palindromic radius of center $$$i$$$ if the substring of length $$$2r+1$$$ centered at $$$i$$$ is a palindrome.

For each center $$$i$$$, find the palindromic radius such that the corresponding palindromic substring is lexicographically smallest.

Input

There are multiple test cases.

The first line contains a single integer $$$T$$$ $$$(1\le T\le10^6)$$$, denoting the number of test cases.

For each test case, there is a single line containing a non-empty string $$$s$$$. It is guaranteed that $$$s$$$ consists only of lowercase English letters.

It is guaranteed that $$$\sum|s|\le10^6$$$.

Output

Output $$$T$$$ lines. For each test case, output a line containing $$$|s|$$$ integers, where the $$$i$$$-th integer represents the answer for center $$$i$$$.

Example
Input
2
cabacbc
a
Output
0 0 1 0 0 0 0
0
Note

In the first sample test case, there are three palindromic substrings centered at $$$3$$$, namely b, aba, and cabac. The lexicographically smallest among them is aba, with a radius of $$$1$$$.