9049: String Magic (Easy Version)

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). 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 one integer which represents f(S).