== include(page="template/taskheader" task_id="numinum") ==

Poveste şi cerinţă...

!{width: 500px; float: center; margin: 35px}problema/numinum?Capture.PNG!
 
Se consideră următoarea structură de date:
 
* În vârful structurii se găseşte fracţia <tex> \frac{1}{1} </tex>
* Din fiecare vârf în care se găseşte fracţia <tex> \frac{p}{q}</tex> se formează alte două fracţii trasând câte 2 segmente de dreaptă astfel: către stânga fracţia <tex> \frac{p}{p+q} </tex> şi către dreapta fracţia <tex> \frac{p+q}{q}</tex>.

h2. Date de intrare

Fişierul de intrare $numinum.in$ ...

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~}, 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$.

h2. Date de ieşire

În fişierul de ieşire $numinum.out$ ...

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~}$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 10000$
* $1 ≤ x{~i~}, y{~i~}, a{~i~}, b{~i~} ≤ 10^9^$

h2. Exemplu
table(example). |_. numinum.in |_. numinum.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 1
  4 3 2 5
| 6

|
h3. Explicaţie

...

$N$ = 1
$x{~1~} = 4, y{~1~} = 3, a{~1~} = 2, b{~1~} = 5$
Pentru a conecta fracţia <tex> \frac{4}{3} </tex> cu fracţia <tex> \frac{2}{5} </tex> avem nevoie de minim 6 segmente, după cum urmează:
$4/3 -> 1/3 -> 1/2 -> 1/1 -> 2/1 -> 2/3 -> 2/5$

== include(page="template/taskfooter" task_id="numinum") ==