DRAGKING - Taming the Dragon

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


Added by:Rony
Date:2018-06-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own

hide comments
2018-07-29 15:00:44 wisfaq
Python users:
to avoid NZEC:
Read T in the following way:
try:
...T=int(raw_input())
except:
...T=0


Last edit: 2018-07-29 15:01:14
2018-07-12 10:17:05 Shubhojeet Chakraborty
long long gives TLE :/
2018-07-01 06:09:31
Why is my solution in cpp-clang getting accepted but same solution in other c++ versions shows runtime error??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.