Fractii

O proprietate interesanta a fractiilor ireductibile este ca orice fractie se poate obtine dupa urmatoarele reguli:

·          pe primul nivel se afla fractia 1/1;
·          pe al doilea nivel, īn stānga fractiei 1/1 de pe primul nivel, plasam fractia 1/2 iar īn dreapta ei fractia 2/1;

nivelul 1:            1/1
nivelul 2:      1/2        2/1

·          pe fiecare nivel k se plaseaza sub fiecare fractie i/j de pe nivelul de deasupra, fractia i/(i+j) īn stānga, iar fractia (i+j)/j īn dreapta.

nivelul 1:              1/1
nivelul 2:      1/2               2/1
nivelul 3:  1/3     3/2       2/3     3/1 

Cerinta

     Dāndu-se o fractie oarecare prin numaratorul si numitorul sau, determinati numarul nivelului pe care se afla fractia sau o fractie echivalenta (avānd aceeasi valoare) cu aceasta.

Date de intrare

Fisier de intrare: FRACTII.IN

Linia 1: N M

·         doua numere naturale nenule, separate printr-un spatiu, reprezentānd numaratorul si numitorul unei fractii (numarator respectiv numitor).

Date de iesire

Fisier de iesire: FRACTII.OUT

Linia 1: niv

·         numar natural nenul, reprezentānd numarul nivelului care corespunde fractiei.

Restrictii

·         1 < N,M <= 2000000000 (doua miliarde)

Exemplu 1

FRACTII.IN
13 8                

FRACTII.OUT
6

Exemplu 2

FRACTII.IN
12 8                

FRACTII.OUT
3

Timp maxim de executare/per test: 1 secunda