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: interview

Starter code:

Solutions:
from fractions import gcd
x, y = map(int, input().split())

a = int(x**.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)

def sqrt(n):
    return n**.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()
# from fractions import gcd
# x, y = map(int, input().split())
#
# a = int(x**.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)


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
        else:
            if 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=list(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)

#print(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)

	
	


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 gcd(a,b):
    #print(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)
    #km = 1
    t += m
    b -= m
    b2 = b
    b //= gcd(a,b)
    a //= gcd(a,b2)
    #print(a,b)
    if a == 1:
        t+=b
        break
print(t)


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)