GNUM - Guess number!

no tags 

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.


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).


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".



1 4 13


2997 40000

hide comments

Added by:Ruslan Sennov
Time limit:0.596s-1.809s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Resource:RCC 2011