Se consideră următoarea structură de date:

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

Cerința

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

Fișierul de intrare numinum.in conține pe prima linie numărul natural N. Pe fiecare dintre următoarele N linii se găsesc câte patru numere naturale x[i], y[i], a[i], b[i], 1 ≤ i ≤ N, 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 x[i] / y[i] cu fracția a[i] / b[i].

Restricții și precizări

• 1 ≤ N ≤ 10 000
• 1 ≤ x[i], y[i], a[i], b[i] ≤ 1 000 000 000, 1 ≤ i ≤ N

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 4/3 cu fracția 2/5 avem nevoie de minimum 6 segmente, după cum urmează: 4/3 → 1/3 → 1/2 → 1/1 → 2/1 → 2/3 → 2/5