MAIN8_D - Coing tossing

no tags 

 

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 expecetd number of times he will have to toss his coin to see that pattern. He wrote this program very quickly. Can you?

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

hide comments
Ouditchya Sinha: 2013-07-13 17:44:41

Good question, but the 2nd test case gave it away. :)

Aman Gupta: 2012-08-26 18:44:25

Nice :) Introduced me to a world of counter-intuitive results while calculating expectations.

Last edit: 2012-08-26 18:45:24
DaRksTar: 2012-07-17 07:10:32

nice ques \m/

Maruti Nandan: 2012-06-26 07:51:44

can someone explain problem better

Santiago Palacio: 2012-04-20 23:03:56

Yes Mathan, that is right.

PubLic_AvenGeR: 2012-04-07 08:53:42

Nice ques...Good approach can lead to AC in 0.00 ..So time limit is a little excessive..

Mathan Kumar: 2012-04-06 18:36:19

Is the third test case right??

Last edit: 2012-04-06 18:53:30
BOND: 2012-02-21 09:25:47

nice problem .

Santiago Palacio: 2011-06-13 21:22:00

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
Pankaj Jindal: 2011-06-13 17:03:07

can someone explain how the answer to second input is 20?


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