Problem C
Hiking Boredom

Bob and Alice are friends. Alice is pleading with Bob to go hiking with her. Bob is not a big hiking fan, but he dislikes Alice’s whining even more, so he reluctantly agrees to join her.

To pass the time during the hike, Bob suggests a game: Alice will give him two integers, the exponent size $E$ and the mantissa size $M$, as well as a binary string of length $1+E+M$. This string represents a floating-point number in an IEEE-like format, where:

• the first bit is the sign bit (the leftmost bit),

• the next $E$ bits form the exponent field,

• the final $M$ bits form the mantissa field.

Figure 1: Example partition of the binary string $11010101$ with field sizes $E=4$ and $M=3$, giving $S_b = 1$, $E_b = 1010$, and $M_b = 101$, where $S_b$, $E_b$, and $M_b$ denote in binary the sign, exponent, and mantissa bit fields, respectively.

Bob will then attempt to convert the binary string into its corresponding value. Before the hike, Bob has asked you to write a program to double-check his answers.

You can convert a binary string to a floating-point number by breaking it down into three parts:

• The first part is calculating if a number is negative or positive:

  \[ Sign = (-1)^{S_b} \]

• The second part is calculating the exponent:

  \[ Exp = 2^{E_b - (2^{E - 1} - 1)} \]

• The final part is calculating the mantissa:

  \[ Man = 1 + \sum _{i=1}^{M} b_{M-i} \cdot 2^{-i} \]

where $b_j$ is the $j$th bit of the mantissa field (with $b_0$ being the rightmost bit).

The final floating-point number is then:

Example.

Given $E=4$, $M=3$, and binary string 11010101:

• $S_b = 1$, so $Sign = (-1)^{1} = -1$

• $E_b = 1010$, which must first be converted from binary:

  \[ E_b = 1010_2 = 10_{10}. \]

  With $E = 4$, we get:

  \[ Exp = 2^{E_b - (2^{E - 1} - 1)} = 2^{10 - (2^{4 - 1} - 1)} = 2^{10 - (8 - 1)} = 2^{3} = 8. \]

• $M_b = 101$, so $b_2 = 1$, $b_1 = 0$, $b_0 = 1$. With $M = 3$, we get:

  \[ Man = 1 + \sum _{i=1}^{3} b_{3-i} \cdot 2^{-i} = 1 + (1 \cdot 2^{-2} + 0 \cdot 2^{-1} + 1 \cdot 2^{-3}) = 1 + (0.5 + 0 + 0.125) = 1.625. \]

Finally, putting it all together:

You do not have to worry about special values (NaN, INF, zero, etc.).

Input

The first line of input contains an integer $n$ ($1 \leq n \leq 1000$) the number of games Bob wants to play.

Each of the next $n$ lines contains three values: the exponent size $E$ ($1 \leq E \leq 6$), the mantissa size $M$ ($1 \leq M \leq 6$), and the binary string $B$, whose length is exactly $1+E+M$.

It is guaranteed that the length of $B$ never exceeds $8$.

Output

Print $n$ lines, each line containing the value represented by the corresponding binary string $B$ based on the exponent and mantissa sizes.

Your answer will be accepted if each value has an absolute error of at most $10^{-10}$ or a relative error of at most $10^{-10}$.

3
4 3 11010101
5 2 01111011
1 6 10111111

-13
57344
-1.984375