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