Se consideră o pereche de numere naturale a și b. Asupra perechii pot fi efectuate următoarele transformări:
  • (a, b) devine (a - b, b);
  • (a, b) devine (a + b, b);
  • (a, b) devine (b, a).


  •     Să se determine numărul minim de transformări succesive care duc la apariția perechii (c, d).

    Fișierul de intrare PAIRS.IN conține două linii. Pe prima linie se află numerele a și b care formează perechea dată, iar pe a doua linie se află numerele c și d care formează perechea care trebuie obținută. Numerele de pe o linie sunt separate prin spații.

    Fișierul de ieșire PAIRS.OUT trebuie să conțină o singură linie pe care se va afla numărul minim de transformări succesive necesare. În cazul în care perechea (c, d) nu poate fi obținută, valoarea scrisă trebuie să fie -1.

  • 0 ≤ a, b, c, d ≤ 1000.


  • PAIRS.IN
    2 2
    2 4

    PAIRS.OUT
    2