Decimal to Fraction

Interview

Time limit1sMemory limit128 MB

Summary

Convert a decimal string, with an optional repeating block in parentheses, into the exact fraction in lowest terms.

Level: Medium5 of 10
Topics: Math, Number theory, String, Implementation
Solved: No attempts yet

Problem

When a rational number is written as a decimal, there are two cases: the decimal has finitely many digits after the point (for example, $1/8 = 0.125$ ), or from some position onward a fixed block of digits repeats forever (for example, $1/11 = 0.090909\ldots$ ).

Given such a decimal, write a program that expresses it as a fraction in lowest terms.

Input

The first line contains the number of test cases, which is at most $100$ . Each of the following lines contains one decimal.

Every decimal begins with 0.. After that come $0$ to $6$ digits, followed by an optional number wrapped in parentheses. The number inside the parentheses has length between $1$ and $9$ and denotes the block of digits that repeats forever.

Each decimal always contains at least one nonzero digit, and the number inside the parentheses is never made up entirely of $0$ s or entirely of $9$ s.

Output

For each test case, print the fraction representation of the given decimal on its own line. The numerator and denominator must be coprime (the fraction must be in lowest terms).

Examples4

Example 1
Input
```
3
0.5
0.(3)
0.6(142857)
```
Expected output
```
1/2
1/3
43/70
```

Example 2

Input

Expected output

Example 3

Input

4
0.(1)
0.(142857)
0.(6)
0.(12)

Expected output

1/9
1/7
2/3
4/33

Example 4

Input

4
0.1(6)
0.16(6)
0.583(3)
0.0(3)

Expected output

1/6
1/6
7/12
1/30