Vasya's Function

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)를 출력한다.