RealPhobia

면접 대비

시간 제한1초메모리 제한128 MB

요약

각 분수 A/B에 대해 D < B이면서 오차 |A/B - C/D|를 최소로 만드는 C/D를 찾고, 오차가 같으면 분모가 가장 작은 것을 고른다.

난이도: 보통10점 중 7점
유형: 정수론, 수학, 이분 탐색, 완전 탐색
정답자: 아직 제출이 없습니다

문제

버트(Bert)는 부동소수점 연산을 정말로 무서워하는 프로그래머입니다. 그는 대신 유리수를 사용해 프로그램을 훌륭하게 작성해 왔지만, 분모가 커지는 것은 싫어합니다.

버트를 도와, 유리수의 분모를 줄이면서 생기는 오차를 최소화하는 프로그램을 작성하세요. $B > 2$ 이고 $0 < A < B$ 인 유리수 $A/B$ 에 대해, 다음 조건을 만족하는 유리수 $C/D$ 를 찾으면 됩니다.

$0 < C < D < B$ 이고,
오차 $\left|\dfrac{A}{B} - \dfrac{C}{D}\right|$ 가 가능한 모든 $C$ , $D$ 중에서 최소이며,
그 최소 오차를 만드는 쌍들 중에서 $D$ 가 가장 작은 양의 정수입니다.

조건 3에서 $D$ 를 최소화하므로, 답 분수 $C/D$ 는 항상 기약분수입니다.

입력

첫째 줄에 테스트 케이스의 개수를 나타내는 정수 $K$ ( $1 < K < 1000$ )가 주어집니다. 이어지는 $K$ 개의 줄에는 각각 하나의 테스트 케이스가 주어지며, 각 테스트 케이스는 두 정수 $A$ 와 $B$ 를 슬래시(/)로 구분한 분수 형태입니다. 이때,

$B$ 는 $2$ 보다 큰 32비트 정수이고,
$0 < A < B$ 입니다.

출력

각 테스트 케이스마다, 분수 $C/D$ 를 두 정수를 슬래시(/)로 구분한 형태로 한 줄에 출력합니다.

예제1

예제 1
입력
```
3
1/4
2/3
13/21
```
예상 출력
```
1/3
1/2
8/13
```