The King of DragonStone is known for his dragons and magic. It can be very hardand dangerous to tame a dragon. So, in order to control his dragons The King speaks random but powerful words. The strength of his words is determined by a strange rule. Rule : Strength of a word is sum of cube of length 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 cubes are 27,8,1,1,1,1. Hence total strength is 39. Given a King's word, find its strength.

Input

First line of input contains an integer T, the number of test cases. Followed by T lines, each line containing a word(say S).(only lowercase letters are allowed).

Constraints:

1 <= length of word <= 1000

1 <= T <= 100

Output

For every word (S), output a single line containing the strength of the word.

Example

Input:

2 

abaa 

dbd 

Output:
39 
30

Note: There is no space between lines