h2. Cerinta

Cunoscand valoarea unui numar natural $n$, realizati un program care determina o pereche de numere naturale $(a,b)$ mai mici sau egale cu $n$, al caror cmmdc se obtine intr-un numar maxim de pasi. Daca exista mai multe perechi $(x,y)$ cu aceasta proprietate se va afisa cea minima. Spunem ca perechea $(a,b)$ este mai mica decat $(x,y)$, daca $a<x$ sau $a=x$ si $b<y$.

Cunoscand valoarea unui numar natural $n$, realizati un program care determina o pereche de numere naturale $(a,b)$ mai mici sau egale cu $n$, al caror cmmdc se obtine intr-un numar maxim de pasi. Daca exista mai multe perechi $(x,y)$ cu aceasta proprietate se va afisa cea minima. Spunem ca perechea $(a,b)$ este mai mica  decat $(x,y)$, daca $a<x$ sau $a=x$ si $b<y$.

h2. Date de intrare

Fisierul de intrare $euclid4.in$ contine un singur numar natural {$n$}.

Fisierul de intrare $euclid4.in$ contine un singur numar natural $n$

h2. Date de iesire