Best Rational Approximation

Many microcontrollers have no floating point unit, but they do have a reasonably fast integer divide unit. On such a chip it pays to approximate a floating point constant with a rational value. For example,

$\frac{355}{113} = 3.1415929203539823008849557522124$

is a quite good approximation to

$\pi = 3.14159265358979323846$

A best rational approximation $p/q$ to a real number $x$ with denominator at most $M$ is a fraction $p/q$ in lowest terms with $q \le M$ such that, for every pair of relatively prime integers $a$ and $b$ with $b \le M$,

$\left| x - \frac{p}{q} \right| \le \left| x - \frac{a}{b} \right|$

holds.

If several fractions in lowest terms satisfy that condition, the answer is the one with the smallest denominator $q$. If the denominators are also equal, the answer is the one with the smallest numerator $p$.

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

The first line contains a single integer $P$ $(1 \le P \le 1000)$, the number of data sets. Every data set is processed in the same way and independently of the others.

Each data set is one line. It contains the data set number $K$ $(1 \le K \le 1000)$, the maximum denominator $M$ $(15 \le M \le 100000)$, and a floating point value $x$ $(0 \le x < 1)$, separated by spaces. The value $x$ is written with a decimal point and has at most 18 digits after it. The leading $0$ before the decimal point may be omitted.

Print one line for each data set. Each line holds the data set number $K$, a single space, the numerator $p$ of the best rational approximation, a forward slash /, and the denominator $q$. The fraction $p/q$ must be in lowest terms.