Wormtongue looked from face to face. In his eyes was the hunted look of a beast seeking some gap in the ring of his enemies.

'Nay, Eomer, you do not fully understand the mind of Master Wormtongue,' said Gandalf, turning his piercing glance upon him. 'He is bold and cunning. Even now he plays a game with peril and wins a throw.' - Gandalf, trying to figure out Wormtongue's mind.

In fact, Wormtongue's mind is a complicated system of evaluating various variables and parameters. In essence, each parameter is a uniform random floating point variable between 0 and 1 (inclusive). Further, his mind works on calculating best and worst-case values, which are equivalent to min/max of 2 expressions.

For example, right now Wormtongue is calculating :

'Chances of escaping' = max('Theoden letting me go', 'Me killing everyone')

'Theoden letting me go' = max('Theoden is forgiving by nature', 'Gandalf advises him to let me go').

'Me killing everyone' = min('Me killing Gandalf', 'Me killing Theoden').

So, you are given an expression consisting of independent uniform [0, 1] random variables, on which you have an expression consisting of "min", and "max" alone. Help Gandalf figure out Wormtongue's mind by finding the expected value of this expression.

Input (STDIN):

The first line contains T, the number of test cases.

Each test case consists of a single line describing the expression. The characters of the string are derived from the set {'M','m','x'}, where 'M' stands for max, 'm' stands for min, and 'x' is a random variable

Formally, in the expression tree, each node which asks for max is labeled as 'M', each node which asks for min is labelled 'm', and all the leaves are labeled 'x'. The description of the expression is preorder traversal of this tree.

For example, Mxmxx describes the expression max(x1, min(x2, x3)).

Output (STDOUT):

For each test case, output one line which contains the expected value of the expression. The results should be accurate within an error range of 10^-6.

Constraints:

1 <= T <= 1,000

1 <= input string length <= 100

Sample Input:

4

x

mxx

Mxx

MmxxMxx 

Sample Output:

0.500000

0.333333

0.666667

0.700000

Notes/Explanation of Sample Input:

For the first test case, it asks for the mean of a random number between 0 and 1, which is 0.5.

Note:

It is recommended to use long long and long double data types in calculation to avoid precision errors.