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$.

3
aaaa
abaaba
ababa

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