최적 유리수 근사

많은 마이크로컨트롤러에는 부동소수점 연산 장치가 없지만 정수 나눗셈 장치는 꽤 빠르다. 이런 환경에서는 부동소수점 상수를 유리수로 근사해서 쓰는 편이 이득이다. 예를 들어

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

는

$\pi = 3.14159265358979323846$

의 꽤 좋은 근사다.

실수 $x$에 대해 분모가 $M$ 이하인 최적 유리수 근사 $p/q$는 다음 조건을 만족하는 기약분수 $p/q$다. $q \le M$이고, $b \le M$이면서 서로소인 모든 정수 $a$, $b$에 대해

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

가 성립한다.

이 조건을 만족하는 기약분수가 여럿이면 분모 $q$가 가장 작은 것을 답으로 하고, 분모까지 같으면 분자 $p$가 가장 작은 것을 답으로 한다.

실수 $x$에 대해 분모가 $M$ 이하인 최적 유리수 근사를 구하는 프로그램을 작성하라.

첫째 줄에 데이터 집합의 개수 $P$ $(1 \le P \le 1000)$가 주어진다. 각 데이터 집합은 같은 방식으로 독립적으로 처리한다.

각 데이터 집합은 한 줄로 이루어진다. 한 줄에는 데이터 집합 번호 $K$ $(1 \le K \le 1000)$, 최대 분모 $M$ $(15 \le M \le 100000)$, 실수 $x$ $(0 \le x < 1)$가 공백으로 구분되어 주어진다. $x$는 소수점을 포함해서 적히며, 소수점 아래 자릿수는 18자리 이하다. 소수점 앞의 $0$은 생략될 수 있다.

각 데이터 집합마다 한 줄씩 출력한다. 각 줄에는 데이터 집합 번호 $K$, 공백 한 칸, 최적 유리수 근사의 분자 $p$, 슬래시 문자 /, 분모 $q$를 차례로 출력한다. $p/q$는 기약분수여야 한다.