Задача D. Doubly-periodic world ≡

Условие

Ученые Флатландии обнаружили, что вселенная, в которой они живут, топологически подобна поверхности тора.

Это значит, что по каждой из осей координат x и y выполняется условие периодичности с периодом Lx и Ly соответственно.
Иначе говоря, точки с координатами (x + u ⋅ Lx, y + v ⋅ Ly) при любых целых u и v являются тождественными.

В целях научного эксперимента из точки с координатами (0, 0) выпускается луч, заданный вектором D⃗ = (dx, dy).
Требуется определить минимальное расстояние, которое пройдет луч прежде чем попасть в исходную точку.

Результат следует записать в единицах измерения, равных длине вектора D⃗,
т.е. найти наименьшее λ  > 0 такое, чтобы при сдвиге на вектор λ  ⋅ D⃗ можно было попасть в исходную точку.

Полученное число должно быть представлено в виде несократимой дроби: λ  = αβ.

Формат входных данных

В начале входных данных хранится число n, за которым следует n запросов,
каждый из которых задается набором целых чисел: Lx_i, Ly_i, dx_i и dy_i.

Формат выходных данных

Выходные данные должны содержать значения α_i и β_i,
полученные в ответ на каждый i-й запрос.

Ограничения

1 ≤ (Lx_i, Ly_i) ≤ 10⁶,  − 10⁶ ≤ (dx_i, dy_i) ≤ 10⁶, |dx_i| + |dy_i| > 0,
1 ≤ n ≤ 10⁵.

Примеры тестов

4

17 18 -6 -8
15 16 6 8
13 14 4 0
10 12 0 2

153 2
10 1
13 4
6 1