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 ≤ 10⁹).

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