题目描述

给定长度为 $n$ 的字符串 $s$，下标从 $1$ 开始。对于每个 $1\le i\le n$，如果以 $i$ 为中心，长度为 $2r+1$ 的子串是回文的，则称非负整数 $r$ 是中心 $i$ 的一个回文半径。

对每个中心 $i$，找到使对应回文子串的字典序最小的回文半径。

输入格式

本题有多组测试数据。

第一行包含一个整数 $T$ ($1\le T\le 10^6$)，表示测试数据组数。

每组数据一行，包含一个非空字符串 $s$。保证 $s$ 仅由小写英文字母构成。

保证 $\sum\lvert s\rvert\le 10^6$。

输出格式

输出 $T$ 行，每行输出 $\lvert s\rvert$ 个整数，其中第 $i$ 个整数表示中心 $i$ 的答案。

样例

2
cabacbc
a

0 0 1 0 0 0 0
0

提示

样例第一组测试中，以 $3$ 为中心的回文子串共有三个，分别是 b、aba、cabac，其中字典序最小者为 aba，半径为 $1$。