Mad scientist Mike is building a time machine in his spare time. To finish the work, he needs a resistor with a certain resistance value.

However, all Mike has is lots of identical resistors with unit resistance R_0 = 1. Elements with other resistance can be constructed from these resistors. In this problem, we will consider the following as elements:   one resistor;  an element and one resistor plugged in sequence;  an element and one resistor plugged in parallel.  [Image] 

With the consecutive connection the resistance of the new element equals R = R_{e} + R_0. With the parallel connection the resistance of the new element equals $R = \frac{1}{\frac{1}{R_{e}} + \frac{1}{R_{0}}}$. In this case R_{e} equals the resistance of the element being connected.

Mike needs to assemble an element with a resistance equal to the fraction $\frac{a}{b}$. Determine the smallest possible number of resistors he needs to make such an element.


-----Input-----

The single input line contains two space-separated integers a and b (1 ≤ a, b ≤ 10^18). It is guaranteed that the fraction $\frac{a}{b}$ is irreducible. It is guaranteed that a solution always exists.


-----Output-----

Print a single number — the answer to the problem.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is recommended to use the cin, cout streams or the %I64d specifier.


-----Examples-----
Input
1 1

Output
1

Input
3 2

Output
3

Input
199 200

Output
200



-----Note-----

In the first sample, one resistor is enough.

In the second sample one can connect the resistors in parallel, take the resulting element and connect it to a third resistor consecutively. Then, we get an element with resistance $\frac{1}{\frac{1}{1} + \frac{1}{1}} + 1 = \frac{3}{2}$. We cannot make this element using two resistors.

Difficulty: competition

Starter code:

Solutions:
a, b = list(map(int, input().split()))
res = 0

while b != 0:
    res += a // b
    a %= b
    a, b = b, a
print(res)


a,b = list(map(int,input().split()))
n = 0
while not (a == 0 or b == 0):
    if a > b:
        n += a // b
        a = a % b
    else:
        n += b // a
        b = b % a
print(n)


def f(a, b):
    if a < b:
        return f(b, a)
    elif b == 1:
        return a
    else:
        return f(b, a%b) + a//b

(a, b) = list(map(int, input().split()))

print(f(a, b))


a,b=list(map(int,input().split()))



def Solve(a,b):
    if(a==(a//b)*b):
        return a//b
    if(a>b):
        ans=0
        ans+=a//b
        a%=b
        if(a==1):
            ans+=b
            return ans
        else:
            ans+=Solve(b,a)
            return ans
    else:
        return Solve(b,a)

print(Solve(a,b))


a, b = [int(x) for x in input().split()]
ans = 0
while (a != 1 and b != 1):
  if (a > b):
    ans += a // b
    a %= b
  a, b = b, a
ans += a+b-1
print(ans)


a=0
a,b=list(map(int,input().split()))



def Solve(a,b):
    if(a==(a//b)*b):
        return a//b
    if(a>b):
        ans=0
        ans+=a//b
        a%=b
        if(a==1):
            ans+=b
            return ans
        else:
            ans+=Solve(b,a)
            return ans
    else:
        return Solve(b,a)

print(Solve(a,b))


a, b = map(int, input().split())
s = 0
while b:
    s += a // b
    a, b = b, a % b
print(s)

#!/usr/bin/env python
# -*- coding: utf-8 -*-

a, b = list(map(int, input().split()))
count = 0
while a > 0 and b > 0:
    if a > b:
        count += (a // b)
        a = a % b
    elif a < b:
        count += (b // a)
        b = (b % a)
    else:
        count += a
        a = b = 0
print(count)


a, b=list(map(int, input().split(' ')))

def perform(a, b):
    steps=0
    while a!=0 and b!=0:
        if a>=b:
            steps+=a//b
        else:
            a, b=b, a
            steps+=a//b
        a, b=b, a%b
    return steps

print(perform(a, b))


a=[0]+[int(i)for i in input().split()]
while a[1]*a[2]!=0:
 a=[a[0]+a[1]//a[2],a[2],a[1]%a[2]]
print(a[0])

import fractions

def resistance():
    #  print("Input the two values")
    _a, _b = input().split()
    a = int(_a)
    b = int(_b)
    answer = 1
    f = fractions.Fraction(a,b)
    one = fractions.Fraction(1,1)

    while (f != one):
        n = f.numerator
        d = f.denominator

        #  If either the num or denom are one, go straight up the line and finish
        if (n == 1) and (d == 1):
            print(answer)
            return
        if (n == 1 ):
            print(answer + d - 1)
            return
        if (d == 1):
            print(answer + n - 1)
            return

        if (f > 1):
            q = n//d
            n = n - q*d
            f = fractions.Fraction(n,d)
            answer = answer + q
        else:
            nbound = (1-f)/f
            n = nbound.numerator
            d = nbound.denominator
            then = n//d + 1
            answer = answer + then
            f = f / (1-then*f)
            
    print(answer)

resistance()


a, b = map(int, input().split())
val = 0
while b > 0:
    a, b, val = b, a % b, val + a // b
print(val)

a, b = (int(x) for x in input().split())
ans = 0
while b:
	ans += a // b
	a %= b
	a, b = b, a
print(ans)


def main():
    a, b = list(map(int, input().split()))
    res = 0
    while b:
        res += a // b
        a, b = b, a % b
    print(res)


def __starting_point():
    main()


__starting_point()

a,b=map(int,input().split())
o=0
while(a and b):
	o=o+max(a,b)//min(a,b)
	if(a>b):a=a%b
	else:b=b%a
print(o)

def f(a, b):
    if a < b:
        return f(b, a)
    elif b == 1:
        return a
    else:
        return f(b, a%b) + a//b

(a, b) = map(int, input().split())

print(f(a, b))

#!/usr/bin/env python3
def solve(a,b):
    assert 1 <= a and 1 <= b
    if a == 1 and b == 1:
        return 1
    else:
        a, b = max(a, b), min(a, b)
        p, q = a // b, a % b
        if q == 0:
            p, q = p-1, 1
        return p + solve(q, b)
a, b = list(map(int,input().split()))
print(solve(a,b))


from functools import reduce
from operator import *
from math import *
from sys import *
from string import *
setrecursionlimit(10**7)
RI=lambda: list(map(int,input().split()))
RS=lambda: input().rstrip().split()
#################################################
n,m=RI()
ans=0
while m:
    ans+=n//m
    n,m= m,n%m
print(ans)



a,b = map(int,input().split())

def res(a,b):
    if a == 1 :
        return b;
    if b == 1 :
        return a;
    q = b//a
    b = b%a
    q += a//b
    return q+res(a%b,b)

print(res(a,b))

a, b = map(int, input().split())
m=max(a,b)
mm=min(a,b)
ans=0
while(mm!=1):
    ans=ans+m//mm
    i=m%mm
    if(i>mm):
        m=i
    else:
        m=mm
        mm=i
ans=ans+m
print(round(ans))

n,m=map(int,input().split())
a=0
while m:a+=n//m;n,m=m,n%m
print(a)

s=input()
[a,b]=(s.split())
a=int(a)
b=int(b)
if b>a: a,b=b,a
ans=0
while b!=0:
    c=a%b
    ans+=(a//b)
    a=b
    b=c
print(ans,end="\n")

s=input()
[a,b]=(s.split())
a=int(a)
b=int(b)
if b>a: a,b=b,a
ans=0
while b!=0:
    c=a%b
    ans+=(a//b)
    a=b
    b=c
print(ans,end="\n")

	 	  	  			 					    			      	

s=input()
[a,b]=(s.split())
a=int(a)
b=int(b)
if b>a: a,b=b,a
ans=0
while b!=0:
    c=a%b
    ans+=(a//b)
    a=b
    b=c
print(ans,end="\n")