Magical Words

Queen of westeros is known for her dragons and magic. To control her dragons she speaks random but powerful words. The strength of her words can be predicted by a strange rule. Rule : Strength of a word is sum of square of size of palindromic substrings in the word. To recall the definition of palindrome, palindrome is a word which reads same when read forward and backward. For example, word "abaa" has 6 palindromic substrings. "aba","aa","a","b","a","a" with sizes 3,2,1,1,1,1 respectively. Their squares are 9,4,1,1,1,1. Hence total strength is 17. Given a queens word ind its strength.

Input

First line of input is T, number of test cases. Followed by T lines, each line containing a word.(only lowercase letters).

Output

Find Strength of each word.

Constraints:

1 <= Size of word <= 1000

1 <= T <=100

Sample Input:

2

abaa

cbc

Sample Output

17

12

Sample Input (Plaintext Link)
2
abaa
cbc

Sample Output (Plaintext Link)
17
12

Explanation
String "cbc" has 4 palindromic substrings, "c", "b", "c" and "cbc" of lengths 1,1,1 and 3. These have squares 1,1,1 and 9 summing up to 12.

Time Limit 1 sec(s) (Time limit is for each input file.)
Memory Limit256 MB
Source Limit1024 KB