Problem Description

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

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

Input Format

This problem has multiple test cases.

The first line contains an integer $T$ ($1 \le T \le 10^6$), which is the number of test cases.

Each test case consists of one line containing a non-empty string $s$. It is guaranteed that $s$ contains only lowercase English letters.

It is guaranteed that $\sum \lvert s \rvert \le 10^6$.

Output Format

Output $T$ lines. For each line, output $\lvert s \rvert$ integers, where the $i$-th integer is the answer for center $i$.

2
cabacbc
a

0 0 1 0 0 0 0
0

Hint

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

Translated by ChatGPT 5