numinum

Se consideră următoarea structură de date:

Figura 1 din enunțul original al problemei numinum.Mărește schema ↗

• În vârful structurii se găsește fracția $\displaystyle \frac{1}{1}$.
• Din fiecare vârf în care se găsește fracția $\displaystyle \frac{p}{q}$ se formează alte două fracții trasând câte 2 segmente de dreaptă astfel: către stânga fracția $\displaystyle \frac{p}{p+q}$ și către dreapta fracția $\displaystyle \frac{p+q}{q}$.

Cerință

Cunoscând numărătorul, respectiv numitorul a două fracții ireductibile diferite din structură, determinați numărul minim de segmente de dreaptă cu care putem conecta în structura dată, cele două fracții.

Date de intrare

Pe prima linie a fişierului de intrare numinum.in se găsește un număr natural $N$. Pe fiecare dintre următoarele $N$ linii se găsesc câte $4$ numere naturale $x_i$, $y_i$, $a_i$, $b_i$, despărțite prin câte un spațiu unde $x_i$, $y_i$ reprezintă numărătorul, respectiv numitorul primei fracții de pe linia $i+1$, iar $a_i$, $b_i$ reprezintă numărătorul, respectiv numitorul celei de-a doua fracții de pe linia $i+1$.

Date de ieșire

Fişierul de ieşire numinum.out va conține $N$ linii. Pe linia $i$ se va scrie numărul minim de segmente de dreaptă necesare pentru a conecta, pe structura dată, fracția $\displaystyle \frac{x_i}{y_i}$ cu fracția $\displaystyle \frac{a_i}{b_i}$.

Restricții și precizări

• $1 \leq N \leq 10 \ 000$;
• $1 \leq x_i, y_i, a_i, b_i \leq 10^9$;

Exemplu

numinum.in

1
4 3 2 5

numinum.out

6

Explicație

$N = 1$, $x_1 = 4$, $y_1 = 3$, $a_1 = 2$, $b_1 = 5$.

Pentru a conecta fracția $\frac{4}{3}$ cu fracția $\frac{2}{5}$, avem nevoie de minim $6$ segmente, după cum urmează:

$\frac{4}{3} \rightarrow \frac{1}{3} \rightarrow \frac{1}{2} \rightarrow \frac{1}{1} \rightarrow \frac{2}{1} \rightarrow \frac{2}{3} \rightarrow \frac{2}{5}$