MAIN8_D - Coing tossing

One day Rohil was getting very bored so he was tossing an unbiased coin randomly. He observed that certain patterns (a sequence of Head and Tail) appear very frequently while some other are very rare. Being a programmer he decided to code a solution which takes a pattern string as input and tells what is the expected number of times he will have to toss his coin to see that pattern. He wrote this program very quickly. Can you?

Input

First line contains (1 <= T <= 25) the number of test cases. Each of following T lines contains a pattern string of 'H' and 'T' only. H is for Head and T is for Tail.

|S| <= 40

Output

For each test case print the output in a new line (it is guaranteed that answer will always be an integer and fits in 64 bit type).

Example

Input:
3
H
HTHT
TTHTHTHTHTHHTHTHTHTTTTTTHTHHHHHTT

Output:
2
20
8589934598

Added by:Mahesh Chandra Sharma
Date:2011-04-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem used for NSIT-IIITA Main contest #8

hide comments
2013-07-13 17:44:41 Ouditchya Sinha
Good question, but the 2nd test case gave it away. :)
2012-08-26 18:44:25 Aman Gupta
Nice :) Introduced me to a world of counter-intuitive results while calculating expectations.

Last edit: 2012-08-26 18:45:24
2012-07-17 07:10:32 DaRksTar
nice ques \m/
2012-06-26 07:51:44 Maruti Nandan
can someone explain problem better
2012-04-20 23:03:56 Santiago Palacio
Yes Mathan, that is right.
2012-04-07 08:53:42 PubLic_AvenGeR
Nice ques...Good approach can lead to AC in 0.00 ..So time limit is a little excessive..
2012-04-06 18:36:19 Mathan Kumar
Is the third test case right??

Last edit: 2012-04-06 18:53:30
2012-02-21 09:25:47 BOND
nice problem .
2011-06-13 21:22:00 Santiago Palacio
If explained, it would be too easy to do the problem, the task is to know how to explain those test cases. The problem statement is very clear.

Last edit: 2011-06-13 21:22:14
2011-06-13 17:03:07 Pankaj Jindal
can someone explain how the answer to second input is 20?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.