Problem E
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$:
\[ |x - p/q| \le |x - 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 |