euclid

Este binecunoscut algoritmul de calcul al celui mai mare divizor comun (cmmdc) cu algoritmul lui Euclid prin împărţiri repetate. Conform acestui algoritm cmmdc a două numere naturale nenule $a$ şi $b$ se calculează păstrând restul împărţirii, şi reluând împărţirea cu vechiul împărţitor şi vechiul rest. Algoritmul se va termina când restul împărţirii devine zero. Cel mai mare divizor comun al celor două numere $a$ şi $b$ va fi ultimul împărţitor.

Pentru calculul celui mai mare divizor comun al perechii ($16$, $22$) se vor efectua succesiv împărţirile:

Vom numi un “pas” o operaţie de împărţire ce intervine în calculului cmmdc. Se observă că pentru determinarea cmmdc($16$, $22$) = $2$ au fost necesari $5$ paşi.

Cerinţă

Cunoscând valoarea unui număr natural $n$, realizaţi un program care determină o pereche de numere naturale ($a$, $b$) mai mici sau egale cu $n$, al căror cmmdc se obţine într-un număr maxim de paşi. Dacă există mai multe perechi ($x$, $y$) cu această proprietate se va afişa cea minimă. Spunem că perechea ($a$, $b$) este mai mică decât ($x$, $y$), dacă $a < x$ sau $a = x$ şi $b < y$.

Date de intrare

Fişierul text euclid.in conţine un singur număr natural $n$.

Date de ieșire

Fişierul text euclid.out va conţine pe prima linie numărul maxim de paşi determinat. A doua linie va conţine un număr natural $a$ reprezentând primul număr al perechii minime identificate, iar pe a treia linie se va scrie numărul $b$ reprezentând al doilea număr din pereche.

Restricții și precizări

• $4 \leq n \leq 10^{200}$;

Exemplul 1

euclid.in

8

euclid.out

5
5
8

Explicație

Numărul maxim de paşi pentru oricare pereche de numere mai mici egale cu $8$ este $5$. Perechea ($5$, $8$) este minimă cu această proprietate.

Exemplul 2

euclid.in

12345678910 

euclid.out

48
4807526976
7778742049

Explicație

Numărul maxim de paşi pentru oricare pereche de numere mai mici egale cu $12 \ 345 \ 678 \ 910$ este $48$. Perechea ($4 \ 807 \ 526 \ 976$, $7 \ 778 \ 742 \ 049$) este minimă cu această proprietate.