# Problem B

Best Rational Approximation

Many microcontrollers have no floating point unit but do have a (reasonably) fast integer divide unit. In these cases it may pay to use rational values to approximate floating point constants. For instance,

\[ 355/113 = 3.1415929203539823008849557522124 \ldots \]is a quite good approximation to

\[ \pi = 3.14159265358979323846 \ldots \]A *best rational approximation* $p/q$ to a real number $x$ with denominator at most
$M$ is a rational number
$p/q$ (in lowest terms)
with $q \le M$ such that,
for any integers $a$ and
$b$ with $b \le M$, and $a$ and $b$ relatively prime, $p/q$ is at least as close to
$x$ as $a/b$:

Write a program to compute the best rational approximation to a real number, $x$, with denominator at most $M$.

## Input

The first line of input contains a single integer $P$, ($1 \le P \le 1\, 000$), which is the number of data sets that follow. Each data set should be processed identically and independently.

Each data set consists of a single line of input. It contains the data set number, $K$, followed by the maximum denominator value, $M$ ($15 \le M \le 1\, 000\, 000$), followed by a real number, $x$, ($0 \le x < 1$), given with at most $18$ digits after the period.

## Output

For each data set there is a single line of output. The single output line consists of the data set number, $K$, followed by a single space followed by the numerator, $p$, of the best rational approximation to $x$, followed by a forward slash (/) followed by the denominator, $q$, of the best rational approximation to $x$.

Sample Input 1 | Sample Output 1 |
---|---|

3 1 100000 0.141592653589793238 2 255 0.141592653589793238 3 15 0.141592653589793238 |
1 14093/99532 2 16/113 3 1/7 |