Please be easy!#12361
Sign in

Please be easy!

1 second
256 megabytes
Easy

Thankfully, you have an easy problem in hand. The problem goes as following:

You are given two integers and and an integer . You are also told that the number of digits needed to represent the numbers and is the same.

solve using bigint or make digit limit high

We define function f(x,y) as

f(x,y)=\underbrace{xxx...x}_{y \text{ times}}

reduce \displaystyle \frac{f(a,k)}{f(b,k)} to an irreducible form

Input

The first line contains an integer t(1 \le t \le 100) —- the number of test cases.

The only line of each test case contains three integers , , and where (1 \le a,b, k \le 10^{15}) — the integers of the problem.

Output

For each test case, output two integers and , where \displaystyle \frac{p}{q} is the irreducible form of the fraction stated above.

Examples

Example 1

Loading
Loading

Note

In the first test case : \displaystyle \frac{22222}{33333}=\frac{2}{3}

In the third test case : \displaystyle \frac{10101010101010101010}{10101010101010101010}=\frac{1}{1}

Scoring

  1. Subtask : ( points) : (a=b)

  2. Subtask : ( points) : (a,b \text{ are coprimes})

  3. Subtask : ( points) : (t = 1 and f(a, k) \le 10^6)

  4. Subtask : ( points) : No additional constraints