DRAGKING - Taming the Dragon

no tags 

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


hide comments
wisfaq: 2018-07-29 15:00:44

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
Shubhojeet Chakraborty: 2018-07-12 10:17:05

long long gives TLE :/

visleck: 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??

aditya12legend: 2018-06-23 15:52:57

Last edit: 2018-06-24 18:15:56

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