Transformari

transformari

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

Fie o pereche de numere întregi oarecare $(X, Y)$. Asupra unei astfel de perechi putem aplica două tipuri de transformări, care au ca rezultat perechile $(X, X+Y)$ sau $(X+Y, Y)$.
 
Se dă un număr întreg $N$. Să se determine numărul minim de transformări necesare pentru a forma o pereche de forma $(x, N)$ sau $(N, x)$, unde $x$ poate fi orice număr întreg.

Fie o pereche de numere întregi oarecare $(X, Y)$.

h2. Date de intrare

Fişierul de intrare $transformari.in$ conţine numărul întreg $N$.

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

h2. Date de ieşire

În fişierul de ieşire $transformari.out$ conţine numărul minim de transformări necesare pentru a ajunge la o pereche de forma dorită.

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

h2. Restricţii

* $1 ≤ N ≤ N$
* Pentru $60%$ din teste $N ≤ 2 000$.

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

h2. Exemplu