Условие:
Окружность единичного радиуса с центром в точке (0, 1) моделирует сечение тоннеля. В точке с координатами (0, 0) находится передатчик сигнала, также в начало координат помещён приемник.
1. Из передатчика в начале координат исходит сигнал, который распространяется вдоль луча ℓ под углом p/q радиан относительно оси x.
2. Когда сигнал достигает окружности, он отражается следующим образом: находится новая точка пересечения b луча ℓ с окружностью и проводится прямая t из точки b к центру окружности. Затем луч ℓ отражается так, что угол между лучом ℓ и прямой t равен углу между новым лучом ℓ′ и прямой t, и сигнал следует вдоль нового луча.
3. Как только сигнал попадает в приемник, расположенный в начале координат, процесс завершается. По нескольким парам целых чисел p и q нужно написать программу, которая для каждой пары определяет, сколько отражений произойдет, прежде чем сигнал попадет в приемник.
Первая строка содержит количество пар целых чисел n (1 ⩽ t ⩽ 105). В последующих n строках даются целые числа pi и qi (1 ⩽ pi, qi ⩽ 1016). Гарантируется, что 0 < pi/qi ⩽ 90 и что наибольший общий делитель pi и qi равен 1.
Для каждой пары (p, q) выведи одно целое число — количество отражений до попадания сигнала в приемник. Можно показать, что в ограничениях задачи это количество является целым числом.
