Hàm $f$ của Vasya

Cho hàm hai biến $f(a,b)$ trên các số nguyên không âm, định nghĩa đệ quy như sau:

• $f(a,0)=0$;
• $f(a,b)=1+f(a,b-gcd(a,b))$ nếu $b>0$, trong đó $gcd(a,b)$ là ước chung lớn nhất của $a$ và $b$.

Cho hai số nguyên dương $x$ và $y$. Hãy tính $f(x,y)$.

Vì giá trị của $f(x,y)$ có thể rất lớn nên tính trực tiếp theo định nghĩa sẽ không khả thi. Bạn cần một thuật toán nhanh hơn.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên $x$ và $y$ ($1\le x,y\le {10}^{12}$).

Dữ liệu ra

In ra một số nguyên là giá trị $f(x,y)$.

Ràng buộc

• $1\le x,y\le {10}^{12}$.

Ví dụ