Вася изучает теорию чисел. Он определил функцию 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). Он хотел сделать это сам, но его способ может занять слишком много времени. Так что он просит вас написать программу, с помощью которой можно посчитать эту функцию быстро.
Выходные данные
Выведите f(x, y).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 5
|
3
|
|
2
|
6 3
|
1
|