Настоящая фобия
Берт — программист, который испытывает настоящий страх перед арифметикой с плавающей запятой. Он успешно использует рациональные числа в своих программах, но не любит, когда знаменатель становится слишком большим. Ваша задача — помочь Берту, написав программу, которая уменьшает знаменатель рационального числа, вводя минимально возможную ошибку. Для рационального числа A/B, где B > 2 и 0 < A < B, ваша программа должна определить рациональное число C/D такое, что:
0 < C < D < B, и
ошибка |A/B - C/D| минимальна среди всех возможных значений C и D, и
D является наименьшим таким положительным целым числом.
Входные данные
Входные данные начинаются с целого числа K (1 ≤ K ≤ 1000), которое обозначает количество случаев. Каждая из следующих K строк описывает один случай и состоит из дроби, представленной двумя целыми числами, A и B, разделенными "/", такими что:
B — это 32-битное целое число, строго большее 2, и
0 < A < B.
Выходные данные
Для каждого случая вывод должен состоять из дроби в строке. Дробь должна быть представлена двумя целыми числами, разделенными "/".