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
hide comments
Ouditchya Sinha:
20130713 17:44:41
Good question, but the 2nd test case gave it away. :) 

Aman Gupta:
20120826 18:44:25
Nice :) Introduced me to a world of counterintuitive results while calculating expectations. Last edit: 20120826 18:45:24 

DaRksTar:
20120717 07:10:32
nice ques \m/


Maruti Nandan:
20120626 07:51:44
can someone explain problem better 

Santiago Palacio:
20120420 23:03:56
Yes Mathan, that is right. 

PubLic_AvenGeR:
20120407 08:53:42
Nice ques...Good approach can lead to AC in 0.00 ..So time limit is a little excessive.. 

Mathan Kumar:
20120406 18:36:19
Is the third test case right?? Last edit: 20120406 18:53:30 

BOND:
20120221 09:25:47
nice problem . 

Santiago Palacio:
20110613 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: 20110613 21:22:14 

Pankaj Jindal:
20110613 17:03:07
can someone explain how the answer to second input is 20? 
Added by:  Mahesh Chandra Sharma 
Date:  20110420 
Time limit:  0.25s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem used for NSITIIITA Main contest #8 