GNUM - Guess number!

There was an application "Guess number!" in one of the popular social network recently. On each of the levels of this offered game it is necessary to define the secret number with some information provided.

In particular, one of the most difficult levels consists in guessing the rational number x (0 < x < 1). It is known, that the result of multiplication of this number by natural number k is exactly one alteration: the i-th and j-th digits after a decimal point are exchanged by each other.

As the number in front of decimal point isn't changed, the inequality 0 < kx < 1 is executed. Initially the numbers after a decimal point can be infinite.

Your problem consists in writing the program which will define value x on numbers i, j, k.

Input

The first input line contains in one integer t (about 1000). Each of the following t  lines contains three numbers: i, j, k (1 ≤ i < j ≤ 1000; 2 ≤ k ≤ 109).

Output

If the required number exists, output consists in two integers — numerator and denominator of a non-reducible fraction setting required number. Otherwise output is "NO SOLUTION".

Example

Input:
1
1 4 13

Output:
2997 40000

Added by:Ruslan Sennov
Date:2011-05-15
Time limit:1s-1.809s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:RCC 2011

hide comments
2021-09-23 06:10:34 David
No java solutions. Please increase time limit for Java. Can complete 1000 test case for i = 2, j = 999, k = 10^9 in in about 1.8 seconds on local PC.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.