String Magic (Hard Version)

Problem Description

Z is learning string theory and he finds a difficult problem. Given a string $S$ of length $n$ (indexed from $1$ to $n$) , define $f(S)$ equal to the number of pair $(i,j)$ that:

• $1 \le i < j \le n$
• $j-i+1=2k, k>0$ ($j-i+1$ is even)
• $S[i,i+k-1]=S[i+k,j]$
• $S[i,i+k-1]$ is a palindrome Here $S[L,R]$ denotes the substring of $S$ with index from $L$ to $R$. A palindrome is a string that reads the same from left to right as from right to left. To solve this problem, Z needs to calculate $f(S[1,i])$ for each $1\le i\le n$. He doesn't know how to solve it, but he knows it's easy for you. Please help him.

Input

The first line contains one integer $T\ (1\le T\le 10)$ which represents the number of test cases. For each test case: One line contains a string $S\ (1\le |S| \le 10^5)$. It's guaranteed that the string only contains lowercase letters.

Output

For each test case: Print one line containing $n$ integers, represents $f(S[1,i])$ for each $1\le i\le n$.

Sample Input

3
aaaa
abaaba
ababa

Sample Output

0 1 2 4
0 0 0 1 1 2
0 0 0 0 0

Source

2023“钉耙编程”中国大学生算法设计超级联赛（5）