Palindromeness

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Let us define the palindromeness of a string in the following way:
 If the string is not a palindrome, its' palindromeness is zero.
 The palindromeness of an oneletter string is 1.
 The palindromness of a string S of the length greater than one is 1 + "palindromeness of the string that is formed by the first [S/2] symbols of S".
Let us consider some examples for better understanding:
 The palindromeness of the string zxqfd is 0, since the string is not a palindrome.
 The palindromeness of the string a is 1, by definition.
 The palindromeness of the string aa is 2, beucase for "aa" we get 1 + palindromeness of "a", that is one, so we get 2.
 The palindromeness of the string abacaba is 3.
You are given a string S. Find the sum of the palindromenesses of all the non empty substrings of S (i.e. S[i..j], where i <= j). In other words, you have to calculate the sum of palindromenesses of N * (N + 1) / 2 substrings of S, where N is the length of S.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of every test case contains a single string S for the corresponding test case.
Output
For each test case, output a single line containing an integer corresponding to the answer to the problem.
Constraints
 1 ≤ T ≤ 3
 S consists only of lowercase Latin letters.
Subtask 1 (15 points):
 1 ≤ S ≤ 100
Subtask 2 (23 points):
 1 ≤ S ≤ 1000
Subtask 3 (62 points):
 1 ≤ S ≤ 10^{5}
Example
Input: 2 zxqfd aba Output: 5 5
Explanation
Example case 1: There is no palindrome that occurs as the substring of zxqfd and has the length more than 1. The individual characters are palindromes of the palindromeness of 1.
Example case 2: The palindromeness of aba is 2 and the sum of the palindromenesses of single characters is 3.
Author:  xcwgf666 
Tester:  karanaggarwal 
Editorial  http://discuss.codechef.com/problems/PALPROB 
Tags  dfs, ltime23, mediumhard, palindrome, xcwgf666 
Date Added:  10032015 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 