Справжня фобія#3047
Берт — програміст, який дуже боїться обчислень із числами з плаваючою крапкою. Він надає перевагу раціональним числам у своїх програмах, але йому не подобається, коли знаменник стає надто великим. Ваше завдання — допомогти Берту, написавши програму, яка зменшує знаменник раціонального числа, вводячи при цьому якомога меншу похибку.
Для раціонального числа , де B > 2 та 0 < A < B, ваша програма повинна знайти раціональне число таке, що:
0 < C < D < B, і
похибка |A/B - C/D| мінімальна серед усіх можливих значень та , і
— найменше таке додатнє ціле число.
Початково задано ціле число (1 \leq K \leq 1000), що означає кількість тестів. Кожен з наступних рядків описує тест у вигляді дробу з двох цілих чисел і , розділених символом "/", таких що:
— -бітне ціле число, строго більше , і
0 < A < B.
Для кожного тесту виведіть в окремому рядку дріб у вигляді двох цілих чисел, розділених символом "/".
Приклад 1