The King of DragonStone is known for his dragons and magic. It can be very hard and 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