Kongo Type

Consider a 32-bit real type with 7 bits from the right as the decimal part, the following 24 bits as the integer part, and the leftmost 1 bit as the sign part as shown below (b1, ..., b32). Represents 0 or 1).

To translate this format into a decimal representation that is easy for humans to understand, interpret it as follows. (-1) Sign part × (integer part + decimal part)

In the above expression, the value of the integer part is b8 + 21 x b9 + 22 x b10 + ... + 223 x b31. For example, the integer part is

If it looks like, the value of the integer part is calculated as follows. 1 + 21 + 23 = 1 + 2 + 8 = 11

On the other hand, the value of the decimal part is (0.5) 1 × b7 ＋ (0.5) 2 × b6 ＋ ... ＋ (0.5) 7 × b1. For example, the decimal part

If it looks like, the decimal part is calculated as follows. 0.51 + 0.53 = 0.5 + 0.125 = 0.625

Furthermore, in the case of the following bit string that combines the sign part, the integer part, and the decimal part,

The decimal number represented by the entire bit string is as follows (where -1 to the 0th power is 1). (-1) 0 × (1 + 2 + 8 + 0.5 + 0.125) = 1 × (11.625) = 11.625

If you enter Q 32-bit bit strings, create a program that outputs the real decimal notation represented by those bit strings without any error.

input

The input consists of one dataset. Input data is given in the following format.

Q s1 s2 .. .. .. sQ

The number of bit strings Q (1 ≤ Q ≤ 10000) is given in the first row. The input bit string si is given in the following Q row. Suppose the input bit string is given in hexadecimal notation (for example, 0111 1111 1000 1000 0000 0000 0000 0000 is given as 7f880000). In other words, each of the Q lines contains eight hexadecimal numbers, which are 4-bit binary numbers, without any blanks. The table below shows the correspondence between decimal numbers, binary numbers, and hexadecimal numbers.

Hexadecimal letters a through f are given in lowercase.

output

Outputs the real decimal notation represented by each bit string line by line. However, in the decimal part, if all the digits after a certain digit are 0, the digits after that digit are omitted. As an exception, if the decimal part is 0, one 0 is output to the decimal part.

Example

Input

8 00000000 80000000 00000080 00000040 000000c0 00000100 80000780 80000f70

Output

0.0 -0.0 1.0 0.5 1.5 2.0 -15.0 -30.875

inputFormat

outputFormat

outputs the real decimal notation represented by those bit strings without any error.

input

The input consists of one dataset. Input data is given in the following format.

Q s1 s2 .. .. .. sQ

The number of bit strings Q (1 ≤ Q ≤ 10000) is given in the first row. The input bit string si is given in the following Q row. Suppose the input bit string is given in hexadecimal notation (for example, 0111 1111 1000 1000 0000 0000 0000 0000 is given as 7f880000). In other words, each of the Q lines contains eight hexadecimal numbers, which are 4-bit binary numbers, without any blanks. The table below shows the correspondence between decimal numbers, binary numbers, and hexadecimal numbers.

Hexadecimal letters a through f are given in lowercase.

output

Outputs the real decimal notation represented by each bit string line by line. However, in the decimal part, if all the digits after a certain digit are 0, the digits after that digit are omitted. As an exception, if the decimal part is 0, one 0 is output to the decimal part.

Example

Input

8 00000000 80000000 00000080 00000040 000000c0 00000100 80000780 80000f70

Output

0.0 -0.0 1.0 0.5 1.5 2.0 -15.0 -30.875

样例

8
00000000
80000000
00000080
00000040
000000c0
00000100
80000780
80000f70

0.0
-0.0
1.0
0.5
1.5
2.0
-15.0
-30.875

</p>