Vasya 正在学习数论。他将函数 f(a, b) 表示为:
- f(a, 0) = 0;
- f(a, b) = 1 + f(a, b - gcd(a, b)),其中 gcd(a, b) 是 a 和 b 的最大公约数。
Vasya 有两个数字 x 和 y,他想要计算 f(x, y)。他尝试自己做,但发现按照他想要的方式计算这个函数可能需要很长时间。所以他决定请你实现一个能够快速计算这个函数的程序。
输入
第一行包含两个整数 x 和 y (1 ≤ x, y ≤ 1012)。
输出
打印 f(x, y)。
示例
输入 #1
3 5
输出 #1
3
输入 #2
6 3
输出 #2
1