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,

is a quite good approximation to

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

3
1 100000 0.141592653589793238
2 255 0.141592653589793238
3 15 0.141592653589793238

1 14093/99532
2 16/113
3 1/7