题目描述

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\le x, y \le 10^{12})$。

输出格式

$f(x, y)$ 的值。

3 5

3

6 3

1