Problem 0D. Doubly-periodic world ≡

Statement

The scientists of Flatland have discovered that the universe they live in is topologically similar to the surface of a torus.

This means that along each coordinate axis x and y, the periodicity condition is satisfied with a respective period Lx and Ly.
In other words, points at coordinates (x + u ⋅ Lx, y + v ⋅ Ly) with any integer values u and v are identical.

For the purpose of a scientific experiment, a ray is emitted from a point with coordinates (0, 0), directed by the vector D⃗ = (dx, dy).
It is required to determine the distance the ray will travel before reaching the initial point.

The result should be expressed in units equal to the length of the vector D⃗,
In other words, the task is to find the minimum coefficient λ  > 0, such that by shifting the vector, one can reach the initial point.

The obtained number should be represented as an irreducible fraction: λ  = αβ.

Input format

The beginning of the input data contains a natural numbe n, followed by exactly n queries,
each specified by a set of integers: Lx_i, Ly_i, dx_i и dy_i.

Output format

The output data should contain the values α_i и β_i,
obtained in response to each i-th query.

Constraints

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

Sample tests

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

Explanation

Чтобы при сдвиге по координате x получить координату исходной точки,
коэффициент λ должен принимать вид: λ  = fx ⋅ Lxdx, где fx — целое.
Аналогично для координаты y получим λ  = fy ⋅ Lydy, где fy — целое.

Тогда имеет место равенство: fx ⋅ Lxdx = fy ⋅ Lydy, или: fx ⋅ (Lx ⋅ dy) = fy ⋅ (Ly ⋅ dx).

Откуда выразим: fx = НОК(Lx ⋅ dy, Ly ⋅ dx)Lx ⋅ dy = Ly ⋅ dxНОД(Lx ⋅ dy, Ly ⋅ dx)
получив ответ:
λ  = fx ⋅ Lxdx = Lx ⋅ LyНОД(Lx ⋅ dy, Ly ⋅ dx).