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
2
abaa
cbc

SAMPLE OUTPUT
17
12Explanation

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.

见题面

见题面