Вася изучает теорию чисел. Он определил функцию f(a, b) следующим образом:
- f(a, 0) = 0;
- f(a, b) = 1 + f(a, b - gcd(a, b)), где gcd(a, b) это наибольший общий делитель a и b.
У Васи есть два числа x и y, и он хочет вычислить f(x, y). Он хотел сделать это сам, но его способ может занять слишком много времени. Так что он просит вас написать программу, с помощью которой можно посчитать эту функцию быстро.