Wrench Size

Peter works at a factory. He reads a list of wrench sizes and picks the wrench that fits each screw, nut, and bolt. Wrench sizes are written in US customary notation, as fractions of an inch such as 13/16" or 3/8". The same size is also written as a decimal. 13/16" is 0.8125".

The reference sheets for the parts round those decimals in inconsistent ways and print approximations only. Depending on the rounding method, 13/16" appears as 0.812, as 0.813, or as 0.81.

The size Peter is looking for is A/B", where A is a positive integer and B is a power of two. Given the decimal printed on a reference sheet, find the wrench size whose denominator B is the smallest possible power of two.

The first line contains the number of test cases T (1 ≤ T ≤ 100).

Each of the next T lines contains one decimal number, a wrench size as printed on a reference sheet. A number has at most six digits after the decimal point. The decimal point can be absent, it can be followed by no digits, and it can be preceded by no digits. Every input value is greater than 0.

For each test case, print the wrench size on its own line.

Let d be the number of digits written after the decimal point on that line. Trailing zeros count, and d is 0 when no digit follows the point. B is the smallest power of two with this property: some positive integer A makes the exact decimal expansion of A/B, taken to d places by one of round up, round down (truncate), or round to nearest, equal to the input value.

Let A/B be in lowest terms. If B is 1, print A". If B is greater than 1, form the mixed number from the quotient q and the remainder r of A divided by B, then print r/B" when q is 0 and q r/B" when q is greater than 0. The last character is a double quote, the inch mark.

The wrench is at most 10 inches, and a power of two that is at most 128 always works. The pair A, B fixed this way is unique.