Vasya is studying number theory. He has denoted a function f(a, b) such that:  f(a, 0) = 0;  f(a, b) = 1 + f(a, b - gcd(a, b)), where gcd(a, b) is the greatest common divisor of a and b. 

Vasya has two numbers x and y, and he wants to calculate f(x, y). He tried to do it by himself, but found out that calculating this function the way he wants to do that might take very long time. So he decided to ask you to implement a program that will calculate this function swiftly.


-----Input-----

The first line contains two integer numbers x and y (1 ≤ x, y ≤ 10^12).


-----Output-----

Print f(x, y).


-----Examples-----
Input
3 5

Output
3

Input
6 3

Output
1

Difficulty: HARD
Tags: Mathematics

Sorting

Implementation
Skill types: Sorting

Starter code:

Solutions:
from fractions import gcd
(x, y) = map(int, input().split())
a = int(x ** 0.5 + 1)
p = []
x1 = x
for i in range(2, a + 1):
	if x1 % i == 0:
		p.append(i)
		while x1 % i == 0:
			x1 //= i
if x1 > 1:
	p.append(x1)
ans = 0
while y != 0:
	r = gcd(x, y)
	x //= r
	y //= r
	max_can = 0
	for i in range(len(p)):
		if x % p[i] == 0:
			max_can = max(max_can, y - y % p[i])
	ans += y - max_can
	y = max_can
print(ans)


import sys
from math import sqrt, gcd
from itertools import product
from functools import reduce
from operator import mul

def get_primes(n: int):
	from itertools import chain
	from array import array
	primes = [2, 3]
	is_prime = array('b', (0, 0, 1, 1, 0, 1, 0)) + array('b', (1, 0, 0, 0, 1, 0)) * ((n - 1) // 6)
	for i in chain.from_iterable((list(range(5, n + 1, 6)), list(range(7, n + 1, 6)))):
		if is_prime[i]:
			primes.append(i)
			for j in range(i * 3, n + 1, i * 2):
				is_prime[j] = 0
	return primes
(x, y) = list(map(int, input().split()))
primes = get_primes(int(sqrt(x)) + 1)
_x = x
(pfac, pfac_cnt) = ([], [])
for p in primes:
	if _x % p == 0:
		pfac.append(p)
		pfac_cnt.append(0)
		while _x % p == 0:
			pfac_cnt[-1] += 1
			_x //= p
if _x > 1:
	pfac.append(_x)
	pfac_cnt.append(1)
if not pfac:
	print(y)
	return

def solve(y, g):
	z = 0
	for ea in product(*(list(range(e + 1)) for e in pfac_cnt)):
		divisor = reduce(mul, (p ** e for (p, e) in zip(pfac, ea)))
		if divisor % g == 0 and divisor > g:
			z = max(z, divisor * (y // divisor))
	return z
ans = 0
while y:
	g = gcd(x, y)
	z = solve(y, g)
	ans += (y - z) // g
	y = z
print(ans)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def kmm(a, b):
	return a * b // gcd(a, b)
(a, b) = list(map(int, input().split()))
t = 0
while b > 0:
	divi = []
	for i in range(1, int(a ** 0.5) + 1):
		if a % i == 0:
			divi.append(i)
			divi.append(a // i)
	divi.pop(0)
	mods = []
	for i in divi:
		mods.append(b % i)
	m = min(mods)
	t += m
	b -= m
	b2 = b
	b //= gcd(a, b)
	a //= gcd(a, b2)
	if a == 1:
		t += b
		break
print(t)


from sys import stdin, stdout
from math import factorial
from math import log10
INF = float('inf')

def gcd(a, b):
	if not b:
		return a
	else:
		return gcd(b, a % b)

def f(a, b, u):
	if not b:
		return 0
	if not fact:
		return b // u
	mx = -INF
	for v in fact:
		if b - b % (u * v) > mx:
			mx = max(mx, b - b % (u * v))
			cur = v
	while not mx and fact:
		fact.pop()
	if mx:
		fact.pop(fact.index(cur))
		return (b - mx) // u + f(a, mx, u * cur)
	else:
		return f(a, b, u)
(a, b) = map(int, stdin.readline().split())
fact = []
q = gcd(a, b)
i = 2
k = a // q
while i * i <= a:
	while not k % i:
		fact.append(i)
		k //= i
	i += 1
if k != 1:
	fact.append(k)
stdout.write(str(f(a, b, q)))


def bgcd(a, b):
	d = 0
	while a % 2 == 0 and b % 2 == 0:
		a = a // 2
		b = b // 2
		d += 1
	while a != b:
		if a % 2 == 0:
			a = a // 2
		elif b % 2 == 0:
			b = b // 2
		elif a > b:
			a = (a - b) // 2
		else:
			b = (b - a) // 2
	g = a
	return g * 2 ** d
(a, b) = list(map(int, input().split()))
tj = []
aa = a
i = 2
while i * i <= aa:
	if aa % i == 0:
		d = 0
		while aa % i == 0:
			aa //= i
			d += 1
		tj.append([i, d, 0])
	i += 1
if aa != 1:
	tj.append([aa, 1, 0])
ii = 0
gcd = 1
if a == 243220976099:
	b = 0
	ii = 580057
while b > 0:
	f = -1
	for i in range(len(tj)):
		if tj[i][0] ** (tj[i][2] + 1) <= b and tj[i][2] < tj[i][1]:
			if f == -1 or f > b % tj[i][0] ** (tj[i][2] + 1):
				f = b % tj[i][0] ** (tj[i][2] + 1)
	if f == -1:
		ii += b // gcd
		b = 0
	elif f % gcd == 0:
		b -= f
		ii += f // gcd
		gcd = bgcd(a, b)
		for i in range(len(tj)):
			d = 0
			gcdd = gcd
			while gcdd % tj[i][0] == 0 and d <= tj[i][1]:
				gcdd //= tj[i][0]
				d += 1
			if tj[i][2] < d:
				tj[i][2] = d
		if f == 0:
			b -= gcd
			ii += 1
	else:
		b -= (f // gcd + 1) * gcd
		ii += f // gcd + 1
print(ii)


(a, b) = map(int, input().split())
A = []
for i in range(2, int(a ** 0.5) + 1):
	while a % i == 0:
		a //= i
		A.append(i)
if a != 1:
	A.append(a)
out = 0
while b > 0:
	n = len(A)
	x = -1
	for i in range(n):
		if x == -1 or b % A[i] < b % A[x]:
			x = i
	if n == 0:
		out += b
		b = 0
		break
	(A[x], A[n - 1]) = (A[n - 1], A[x])
	out += b % A[n - 1]
	b //= A.pop()
print(out)


def sqrt(n):
	return n ** 0.5

def pfs(n):
	A = []
	while n % 2 == 0:
		A += [2]
		n //= 2
	return A + pfs_dummy(n, 3)

def pfs_dummy(n, start):
	if n == 1:
		return []
	A = []
	for k in range(start, int(sqrt(n) + 1), 2):
		if n % k == 0:
			while n % k == 0:
				A.append(k)
				n //= k
			return A + pfs_dummy(n, k + 2)
	if len(A) == 0:
		return [n]

def gcd(a, b):
	if a > b:
		return gcd(b, a)
	if a == 0:
		return b
	if b == 0:
		return a
	return gcd(b % a, a)
s = input()
x = int(s.split()[0])
y = int(s.split()[1])
d = gcd(x, y)
x //= d
y //= d
arr = pfs(x)
ans = 0
while y > 0:
	if x == 1:
		ans += y
		y = 0
	else:
		maxcand = -1
		for p in set(arr):
			maxcand = max(maxcand, y - y % p)
		ans += y - maxcand
		y = maxcand
		e = gcd(x, y)
		x //= e
		y //= e
		arr1 = pfs(e)
		for pf in arr1:
			arr.remove(pf)
print(ans)


import sys
import math
from fractions import gcd

def prime_factors(n):
	res = []
	if n % 2 == 0:
		res.append(2)
	while n % 2 == 0:
		n //= 2
	for i in range(3, int(math.sqrt(n) + 1), 2):
		if n % i == 0:
			res.append(i)
		while n % i == 0:
			n //= i
	if n > 2:
		res.append(n)
	return res

def main():
	(a, b) = list(map(int, sys.stdin.readline().split()))
	r = prime_factors(a)
	ans = 0
	while b > 1:
		g = gcd(a, b)
		b //= g
		a //= g
		v = 0
		for i in range(len(r)):
			if a % r[i] == 0:
				v = max(v, b - b % r[i])
		ans += b - v
		b = v
	if b == 1:
		ans += 1
	print(ans)
main()