This page is still under construction.

Parts of this page are still being built. What you see may change.

Fraction to Repeating Decimal

Interview

Time limit1sMemory limit256 MB

Summary
Write each given fraction as its decimal form with the shortest nonrepeating part and the repeating block in parentheses.
Level

Medium5 of 10

Topics
Hash map, Math, Simulation
Solved
No attempts yet

Problem

Every rational number can be written as a repeating decimal, where from some position on the same block of digits repeats forever.

13=39=0.3333333⋯=0.3‾\frac{1}{3} = \frac{3}{9} = 0.3333333\dots = 0.\overline{3}

17=142857999999=0.14285714285714⋯=0.142857‾\frac{1}{7} = \frac{142857}{999999} = 0.14285714285714\dots = 0.\overline{142857}

314=21428559999990=0.2142857142857⋯=0.2142857‾\frac{3}{14} = \frac{2142855}{9999990} = 0.2142857142857\dots = 0.2\overline{142857}

The denominators above are made of nothing but 9s and 0s, and that pattern is exactly the standard recipe for turning a repeating decimal back into a fraction. Starting from an arbitrary fraction, that recipe is hard to apply, so the usual way to convert a fraction into a repeating decimal is repeated long division. Doing it by hand takes a lot of work, so write a program that does it for you.

Input

The first line contains the number of test cases TT (1≤T≤150001 \le T \le 15000).

Each of the next TT lines contains a numerator aa and a denominator bb as integers separated by a space, with 0≤a<10240 \le a < 1024 and 0<b<10240 < b < 1024.

Output

For each test case, print the repeating decimal of a/ba/b on its own line.

Write the integer part, a period, the non-repeating fractional digits, then the repeating block wrapped in parentheses. When the non-repeating part is empty, the opening parenthesis comes right after the period. A fraction whose division comes out even still gets (0)(0), because zeros repeat forever after the last digit. Take the shortest possible non-repeating part and the shortest possible repeating block.

Examples1

  1. Example 1

    Input
    6
1 2
1 7
10 5
11 5
995 476
991 994
    Expected output
    0.5(0)
0.(142857)
2.(0)
2.2(0)
2.09(033613445378151260504201680672268907563025210084)
0.9(969818913480885311871227364185110663983903420523138832997987927565392354124748490945674044265593561368209255533199195171026156941649899396378269617706237424547283702213279678068410462776659959758551307847082494)