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 ≤ i < j ≤ 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 ≤ i ≤ n.
He doesn’t know how to solve it, but he knows it’s easy for you. Please help him.
输入格式
The first line contains one integer T (1 ≤ T ≤ 10) which represents the number of test cases.
For each test case: One line contains a string S (1 ≤ |S| ≤ 105
).
It’s guaranteed that the string only contains lowercase letters.
输出格式
For each test case: Print one line containing n integers, represents f(S[1, i]) for each 1 ≤ i ≤ n.