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.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Number theory

Mathematics


Solutions:
(a, b) = map(int, input().split())
res = 0
while b > 0:
	(d, m) = (a // b, a % b)
	res += d
	(a, b) = (b, m)
print(res)


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

def fun(a, b):
	if a < b:
		return fun(b, a)
	if a % b == 0:
		return a // b
	return a // b + fun(b, a % b)
print(fun(a, b))


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))


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase

def main():
	(a, b) = [int(x) for x in input().split()]
	numOfSolutions = 0
	while a > 0 and b > 0:
		if a > b:
			numOfResistorsToRemove = (a - b) // b + 1
			a -= b * numOfResistorsToRemove
			numOfSolutions += numOfResistorsToRemove
		elif a < b:
			numOfResistorsToRemove = (b - a) // a + 1
			b -= a * numOfResistorsToRemove
			numOfSolutions += numOfResistorsToRemove
		else:
			numOfSolutions += a
			break
	print(numOfSolutions)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
input = lambda : sys.stdin.readline().rstrip('\r\n')

def print(*args, **kwargs):
	sep = kwargs.pop('sep', ' ')
	file = kwargs.pop('file', sys.stdout)
	atStart = True
	for x in args:
		if not atStart:
			file.write(sep)
		file.write(str(x))
		atStart = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
main()


def gcd(a, b):
	return 0 if b == 0 else a // b + gcd(b, a % b)
print(gcd(*(int(x) for x in input().split())))


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


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


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


f = lambda a, b: b // a + f(b % a, a) if a else 0
print(f(*sorted(map(int, input().split()))))


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest
INF = 999999999999999999999999
alphabets = 'abcdefghijklmnopqrstuvwxyz'

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

class SegTree:

	def __init__(self, n):
		self.N = 1 << n.bit_length()
		self.tree = [0] * (self.N << 1)

	def update(self, i, j, v):
		i += self.N
		j += self.N
		while i <= j:
			if i % 2 == 1:
				self.tree[i] += v
			if j % 2 == 0:
				self.tree[j] += v
			(i, j) = (i + 1 >> 1, j - 1 >> 1)

	def query(self, i):
		v = 0
		i += self.N
		while i > 0:
			v += self.tree[i]
			i >>= 1
		return v

def SieveOfEratosthenes(limit):
	isPrime = [True] * (limit + 1)
	isPrime[0] = isPrime[1] = False
	primes = []
	for i in range(2, limit + 1):
		if not isPrime[i]:
			continue
		primes += [i]
		for j in range(i * i, limit + 1, i):
			isPrime[j] = False
	return primes

def main():
	mod = 1000000007
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	for _ in range(tc):
		(a, b) = ria()
		op = 0
		while True:
			if b:
				op += a // b
				a %= b
				(a, b) = (b, a)
			else:
				break
		wi(op)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


(a, b) = map(int, input().split())
count = 0
while a > 1:
	count += a // b
	a = a % b
	temp = a
	a = b
	b = temp
print(count + a * b)


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))


(a, b) = 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)


(a, b) = map(int, input().split())
p = 0
if a == 1:
	print(b)
	exit()
while a != 1:
	if a > b:
		p += a // b
		k = a // b
		a = a - k * b
	elif a < b:
		(a, b) = (b, a)
	else:
		p += 1
		break
if a == 1 and b != a:
	p += b
print(p)


import random

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

def lcm(a, b):
	return a * b / gcd(a, b)
(x, y) = map(int, input().split())
ans = 0
while x and y:
	if x >= y:
		ans += x // y
		x %= y
	else:
		ans += y // x
		y %= x
print(ans)


(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, b) = [int(x) for x in input().split()]
ans = 0
while 1:
	if a == 0 or b == 0:
		break
	ans += a // b
	a = a % b
	(a, b) = (b, a)
print(ans)


def aise(a, b):
	if a == 0:
		return 0
	return b // a + aise(b % a, a)
(a, b) = map(int, input().split())
print(aise(a, b))


inp = input()
(a, b) = (int(inp.split()[0]), int(inp.split()[1]))
from math import floor
Sum = 0

def work(a, b):
	global Sum
	if a // b >= 1 and a / b > 0:
		Sum += a // b
		work(a % b, b)
	elif a // b < 1 and a / b > 0:
		work(b, a)
	elif a / b == 1:
		Sum += 1
work(a, b)
print(Sum)


def dfs(a, b):
	if b == 1:
		return a
	if a == 1:
		return b
	if a > b:
		return a // b + dfs(a % b, b)
	return b // a + dfs(a, b % a)
(a, b) = map(int, input().split())
print(dfs(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())
val = 0
while b > 0:
	(a, b, val) = (b, a % b, val + a // b)
print(val)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
(a, b) = l()
c = 0
while a > 0 and b > 0:
	c += a // b
	(a, b) = (b, a % b)
print(c)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7

def solve():
	(a, b) = getInts()
	ans = 1
	while a != 1 or b != 1:
		if a > b:
			steps = a // b - 1 if a % b == 0 else a // b
			a -= steps * b
		else:
			steps = b // a - 1 if b % a == 0 else b // a
			b -= steps * a
		ans += steps
	return ans
print(solve())


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) = map(int, input().split())
print(solve(a, b))


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


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


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


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])


(a, b) = map(int, input().split(' '))
res = 0
temp = 0
if a % b == 0:
	print(int(a / b))
else:
	while b != 0:
		res += a // b
		a %= b
		temp = a
		a = b
		b = temp
	print(res)


from __future__ import division, print_function
import math
import os
import sys
from fractions import *
from sys import *
from decimal import *
from io import BytesIO, IOBase
from itertools import *
from collections import *
M = 10 ** 9 + 7
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def inpu():
	return int(inp())

def regularbracket(t):
	p = 0
	for i in t:
		if i == '(':
			p += 1
		else:
			p -= 1
		if p < 0:
			return False
	else:
		if p > 0:
			return False
		else:
			return True

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] <= key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def reverse1(string):
	pp = ''
	for i in string[::-1]:
		pp += i
	if pp == string:
		return True
	return False

def reverse2(list1):
	l = []
	for i in list1[::-1]:
		l.append(i)
	if l == list1:
		return True
	return False

def mex(list1):
	p = max(list1) + 1
	for i in range(len(list1)):
		if list1[i] != i:
			p = i
			break
	return p

def sumofdigits(n):
	n = str(n)
	s1 = 0
	for i in n:
		s1 += int(i)
	return s1

def perfect_square(n):
	s = math.sqrt(n)
	if s == int(s):
		return True
	return False

def roman_number(x):
	if x > 15999:
		return
	value = [5000, 4000, 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
	symbol = ['F', 'MF', 'M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I']
	roman = ''
	i = 0
	while x > 0:
		div = x // value[i]
		x = x % value[i]
		while div:
			roman += symbol[i]
			div -= 1
		i += 1
	return roman

def soretd(s):
	for i in range(1, len(s)):
		if s[i - 1] > s[i]:
			return False
	return True

def countRhombi(h, w):
	ct = 0
	for i in range(2, h + 1, 2):
		for j in range(2, w + 1, 2):
			ct += (h - i + 1) * (w - j + 1)
	return ct

def countrhombi2(h, w):
	return h * h // 4 * (w * w // 4)

def binpow(a, b):
	if b == 0:
		return 1
	else:
		res = binpow(a, b // 2)
	if b % 2 != 0:
		return res * res * a
	else:
		return res * res

def binpowmodulus(a, b, m):
	a %= m
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % m
		a = a * a % m
		b >>= 1
	return res

def coprime_to_n(n):
	result = n
	i = 2
	while i * i <= n:
		if n % i == 0:
			while n % i == 0:
				n //= i
			result -= result // i
		i += 1
	if n > 1:
		result -= result // n
	return result

def prime(x):
	if x == 1:
		return False
	else:
		for i in range(2, int(math.sqrt(x)) + 1):
			if x % i == 0:
				return False
		else:
			return True

def luckynumwithequalnumberoffourandseven(x, n, a):
	if x >= n and str(x).count('4') == str(x).count('7'):
		a.append(x)
	elif x < 1000000000000.0:
		luckynumwithequalnumberoffourandseven(x * 10 + 4, n, a)
		luckynumwithequalnumberoffourandseven(x * 10 + 7, n, a)
	return a

def luckynuber(x, n, a):
	p = set(str(x))
	if len(p) <= 2:
		a.append(x)
	if x < n:
		luckynuber(x + 1, n, a)
	return a

def interact(type, x):
	if type == 'r':
		inp = input()
		return inp.strip()
	else:
		print(x, flush=True)

def findTrailingZeros(n):
	count = 0
	while n >= 5:
		n //= 5
		count += n
	return count

def mergeSort(arr):
	if len(arr) > 1:
		mid = len(arr) // 2
		L = arr[:mid]
		R = arr[mid:]
		mergeSort(L)
		mergeSort(R)
		i = j = k = 0
		while i < len(L) and j < len(R):
			if L[i] < R[j]:
				arr[k] = L[i]
				i += 1
			else:
				arr[k] = R[j]
				j += 1
			k += 1
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1
		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1
res = set()

def solven(p, l, a, b, n):
	if p > n or l > 10:
		return
	if p > 0:
		res.add(p)
	solven(p * 10 + a, l + 1, a, b, n)
	solven(p * 10 + b, l + 1, a, b, n)

def subsetsUtil(A, subset, index, d):
	print(*subset)
	s = sum(subset)
	d.append(s)
	for i in range(index, len(A)):
		subset.append(A[i])
		subsetsUtil(A, subset, i + 1, d)
		subset.pop(-1)
	return d

def subsetSums(arr, l, r, d, sum=0):
	if l > r:
		d.append(sum)
		return
	subsetSums(arr, l + 1, r, d, sum + arr[l])
	subsetSums(arr, l + 1, r, d, sum)
	return d

def print_factors(x):
	factors = []
	for i in range(1, x + 1):
		if x % i == 0:
			factors.append(i)
	return factors

def calc(X, d, ans, D):
	if len(X) == 0:
		return
	i = X.index(max(X))
	ans[D[max(X)]] = d
	Y = X[:i]
	Z = X[i + 1:]
	calc(Y, d + 1, ans, D)
	calc(Z, d + 1, ans, D)

def factorization(n, l):
	c = n
	if prime(n) == True:
		l.append(n)
		return l
	for i in range(2, c):
		if n == 1:
			break
		while n % i == 0:
			l.append(i)
			n = n // i
	return l

def good(b):
	l = []
	i = 0
	while len(b) != 0:
		if b[i] < b[len(b) - 1 - i]:
			l.append(b[i])
			b.remove(b[i])
		else:
			l.append(b[len(b) - 1 - i])
			b.remove(b[len(b) - 1 - i])
	if l == sorted(l):
		return True
	return False

def generate(st, s):
	if len(s) == 0:
		return
	if s not in st:
		st.add(s)
		for i in range(len(s)):
			t = list(s).copy()
			t.remove(s[i])
			t = ''.join(t)
			generate(st, t)
	return

def largestincreasingsubsequence(A):
	l = [1] * len(A)
	sub = []
	for i in range(1, len(l)):
		for k in range(i):
			if A[k] < A[i]:
				sub.append(l[k])
		l[i] = 1 + max(sub, default=0)
	return max(l, default=0)

def findOR(nums, N):
	prefix_sum = 0
	result = 0
	for i in range(N):
		result |= nums[i]
		prefix_sum += nums[i]
		result |= prefix_sum
	return result

def OR(a, n):
	ans = a[0]
	for i in range(1, n):
		ans |= a[i]
	return ans

def main():
	(a, b) = sep()
	cnt = 0
	while b != 0:
		cnt += a // b
		(a, b) = (b, a % b)
	print(cnt)
main()


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

def f(a, b):
	if a == b:
		return 1
	elif a == 1:
		return b
	elif b == 1:
		return a
	elif a > b:
		s = a // b
		rem = a - s * b
		return s + f(rem, b)
	else:
		s = b // a
		rem = b - s * a
		return s + f(rem, a)
print(f(a, b))


(a, b) = map(int, input().split())
k = 1
while a != b:
	if a > b:
		x = a // b - (b == 1)
		k += x
		a -= b * x
	else:
		x = b // a - (a == 1)
		k += x
		b -= a * x
print(k)


import math as m

def f(a, b):
	return a if b == 1 else a // b + f(b, a % b)
(n, m) = map(int, input().split())
print(f(n, m))


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


import sys

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
(a, b) = get_ints()
ans = 0
while a:
	ans += b // a
	(a, b) = (b % a, a)
print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def getint():
	return int(input())

def getints():
	return list(map(int, input().split()))

def getint1():
	return list(map(lambda x: int(x) - 1, input().split()))

def main():
	(a, b) = getints()
	print(result(a, b))

def result(a, b):
	if a == 0:
		return 0
	return b // a + result(b % a, a)
main()


def resistors(a, b):
	ans = 0
	while b:
		ans += a // b
		(a, b) = (b, a % b)
	return ans
(a, b) = map(int, input().strip().split())
print(resistors(a, b))


import os
import sys
from io import BytesIO, IOBase
from math import log2, ceil, sqrt, gcd, log
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
g = lambda : input().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
(n, d) = gil()

def solve(n, d):
	if n == 0 or d == 0:
		return 0
	md = n % d
	return n // d + solve(max(md, d), min(md, d))
ans = solve(max(n, d), min(n, d))
print(ans)


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


def sol(a, b):
	global ans
	ans += a // b
	a = a % b
	if a == 0:
		return 0
	return sol(b, a)
ans = 0
(a, b) = map(int, input().split())
sol(max(a, b), min(a, b))
print(ans)


(n, m) = map(int, input().split())
res = 0
while min(n, m) > 0:
	if n >= m:
		res += n // m
		n %= m
	else:
		res += m // n
		m %= n
print(res)


import math
import sys
import collections
import bisect
import string
import time

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	ans = []
	for p in range(n + 1):
		if prime[p]:
			ans.append(p)
	return ans
primes = SieveOfEratosthenes(2 * 10 ** 5)
set_primes = set(primes)
for t in range(1):
	(a, b) = get_ints()
	ans = 0
	while a > 0 and b > 0:
		ans += max(a, b) // min(a, b)
		(a, b) = (max(a, b) % min(a, b), min(a, b))
	print(ans)


import sys
import math as mt
import bisect

def solve(a, b):
	ans = 1
	while a > 1 or b > 1:
		if a == 1 or b == 1:
			ans += max(a, b) - 1
			a = 1
			b = 1
			break
		if a > b:
			mul = a // b
			ans += mul
			a -= mul * b
		else:
			mul = b // a
			ans += mul
			b -= mul * a
	return ans
t = 1
for __ in range(t):
	(a, b) = map(int, input().split())
	print(solve(a, b))


from math import *
(a, b) = map(int, input().split())
s = 0
while a != 0 and b != 0:
	if b > a:
		s += b // a
		b %= a
	else:
		s += a // b
		a %= b
print(s)


def gcd(a, b, count):
	if b == 0:
		return count
	else:
		return gcd(b, a % b, count + a // b)
(a, b) = list(map(int, input().split()))
res = a // b
a = a % b
print(res + gcd(a, b, 0))


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


from math import ceil
from math import floor
from math import sqrt
from math import log
prime = pow(10, 9) + 7

def mod_expo(n, p, m):
	result = 1
	while p != 0:
		if p % 2 == 1:
			result = result * n % m
		p //= 2
		n = n * n % m
	return result

def find_sequences(n):
	result = []
	if n <= 3:
		return result
	while n > 5:
		result.append('24 * 1 = 24')
		result.append(str(n) + ' - ' + str(n - 1) + ' = 1')
		n -= 2
	result.reverse()
	if n == 4:
		result.insert(0, '1 + 2 = 3')
		result.insert(1, '3 + 3 = 6')
		result.insert(2, '4 * 6 = 24')
	elif n == 5:
		result.insert(0, '1 + 4 = 5')
		result.insert(1, '5 * 5 = 25')
		result.insert(2, '25 - 3 = 22')
		result.insert(3, '22 + 2 = 24')
	return result

def check(n, k):
	v = 0
	left = n
	while left > 0:
		current = min(left, k)
		v += current
		left -= current
		left -= left // 10
	return 2 * v >= n

def get_pair_count(n, arr):
	count = 0
	mp = {}
	for i in range(n):
		if arr[i] not in mp:
			mp[arr[i]] = 0
		mp[arr[i]] += 1
	for i in range(n):
		for deg in range(1, 31):
			val = pow(2, deg) - arr[i]
			if val in mp:
				count += mp[val]
				if val == arr[i]:
					count -= 1
		mp[arr[i]] -= 1
	return count

def find_bsearch(n):
	left = 1
	right = n
	middle = 0
	if n <= 2:
		return 1
	while left < right:
		middle = left + (right - left) // 2
		if check(n, middle):
			if middle == left or not check(n, middle - 1):
				return middle
			right = middle - 1
		else:
			left = middle + 1
	return left

def count_resistors(a, b):
	level = -1
	while b:
		(cont, a) = divmod(a, b)
		level += cont
		(a, b) = (b, a)
	if a == 1:
		return level + 1
	return -1

def find_min(N, d):
	N = str(N)
	d = str(d)
	for i in range(len(N) - 1, -1):
		print(N[i])
		if int(N[i]) > int(d):
			N = ''.join([N[j] for j in range(len(N)) and j != i])
			N += d
	return N
t = 1
while t:
	t = t - 1
	count = 0
	(n, X) = map(int, input().split())
	print(count_resistors(n, X))


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')


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


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

def calc(a, b):
	if a <= 0 or b <= 0:
		return 0
	if a == 1:
		return b
	if b == 1:
		return a
	if a >= b:
		return a // b + calc(a % b, b)
	return b // a + calc(a, b % a)
print(calc(a, b))


def check(m, n):
	if m >= 1 / n - 1:
		return False
	return True

def binsear(n):
	high = 10 ** 40
	low = 0
	mid = (high + low) // 2
	while high >= low:
		if check(mid, n):
			low = mid + 1
		else:
			high = mid - 1
		mid = (high + low) // 2
	return mid + 1
from fractions import Fraction
(a, b) = map(int, input().split())
re = Fraction(a) / Fraction(b)
ans = 0
while re != int(re):
	ans += int(re)
	re -= int(re)
	num = binsear(Fraction(re))
	re /= Fraction(1) - Fraction(num) * Fraction(re)
	ans += num
ans += int(re)
print(ans)


def solve(a, b):
	if a < b:
		return solve(b, a)
	elif b == 1:
		return a
	else:
		return a // b + solve(b, a % b)
inp = input()
arr = inp.split(' ')
a = int(arr[0])
b = int(arr[1])
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)


(x, y) = map(int, input().split())

def sa(x, y):
	div = x // y
	if x == div * y:
		return div
	elif x > y:
		output = 0
		output += div
		x = x % y
		if x == 1:
			output = output + y
			return output
		if x != 1:
			output = output + sa(y, x)
			return output
	else:
		return sa(y, x)
print(sa(x, y))


import sys
input = sys.stdin.readline

def ceil(x):
	if x != int(x):
		x = int(x) + 1
	return x

def factorial(x, m):
	val = 1
	while x > 0:
		val = val * x % m
		x -= 1
	return val

def fact(x):
	val = 1
	while x > 0:
		val *= x
		x -= 1
	return val

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

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

def lcm(a, b):
	return a * b // gcd(a, b)

def nCr(n, k):
	if k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def upper_bound(a, x, lo=0, hi=None):
	if hi == None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if a[mid] < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	(prime[0], prime[1]) = (False, False)
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n // p
			result = result * (1.0 - 1.0 / float(p))
		p = p + 1
	if n > 1:
		result = result * (1.0 - 1.0 / float(n))
	return int(result)

def is_prime(n):
	if n == 0:
		return False
	if n == 1:
		return True
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True
MAXN = int(100000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
spf = [0 for i in range(MAXN)]

def factoriazation(x):
	res = []
	for i in range(2, int(x ** 0.5) + 1):
		while x % i == 0:
			res.append(i)
			x //= i
	if x != 1:
		res.append(x)
	return res

def factors(n):
	res = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			res.append(i)
			res.append(n // i)
	return list(set(res))

def int_array():
	return list(map(int, input().strip().split()))

def float_array():
	return list(map(float, input().strip().split()))

def str_array():
	return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
from itertools import permutations
import math
from bisect import bisect_left

def solve():
	(a, b) = map(int, input().split())
	(a, b) = (min(a, b), max(a, b))
	c = 0
	while a > 0:
		c += b // a
		b = b % a
		(a, b) = (min(a, b), max(a, b))
	print(c)
for _ in range(1):
	solve()


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.stdin = open('input.txt', 'r')
except:
	pass

def pmat(A):
	for ele in A:
		print(*ele, end='\n')

def seive():
	prime = [1 for i in range(10 ** 6 + 1)]
	prime[0] = 0
	prime[1] = 0
	for i in range(10 ** 6 + 1):
		if prime[i]:
			for j in range(2 * i, 10 ** 6 + 1, i):
				prime[j] = 0
	return prime
(a, b) = L()

def rec(a, b):
	if b == 1:
		return a
	if a > b:
		return a // b + rec(b, a % b)
	else:
		return rec(b, a)
print(rec(a, b))
endtime = time.time()


def euclid(a, b, num_iterations=0):
	return euclid(b, a % b, num_iterations + a // b) if b else num_iterations
(a, b) = map(int, input().split())
print(euclid(a, b))


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

def rec(a, b):
	if a // b * b == a:
		return a // b
	if a > b:
		t = a // b
		return t + rec(a - t * b, b)
	else:
		t = b // a
		if a * t == b:
			t -= 1
		return t + rec(a, b - t * a)
print(rec(a, b))


def GCD(a, b, i):
	if a > b:
		(a, b) = (b, a)
	if a == 0 or b == 0:
		return i
	i += b // a
	b = b % a
	return GCD(a, b, i)
(a, b) = [int(x) for x in input().split()]
print(GCD(a, b, 0))


I = lambda : list(map(int, input().split(' ')))
(a, b) = I()
ans = 0
while a > 0 and b > 0 and (a // b > 0) or b // a > 0:
	ans += a // b
	(a, b) = (b, a % b)
print(ans)


(a, b) = map(int, input().split())
ans = 0
while 1:
	ans += a // b
	a = a % b
	if a == 0:
		print(ans)
		exit(0)
	(a, b) = (b, a)


import math
(a, b) = map(int, input().split())
i = 0
while 1:
	if a == b or a == 1 or b == 1:
		if a == b:
			i += 1
		elif a == 1:
			i += b
		else:
			i += a
		break
	elif a % b == 0:
		i += a // b
		break
	elif a > b:
		c = a // b
		i += c
		a = a - c * b
	else:
		c = a
		a = b
		b = c
print(i)


def soprotivlenie(a, b):
	min_res = 0
	while a > 0 and b > 0:
		if a > b:
			min_res += a // b
			a = a % b
		else:
			min_res += b // a
			b = b % a
	return min_res
(x, y) = [int(i) for i in input().split()]
print(soprotivlenie(x, y))


import sys
import math
MAXNUM = math.inf
MINNUM = -1 * math.inf

def getInts():
	return map(int, sys.stdin.readline().rstrip().split(' '))

def getString():
	return sys.stdin.readline().rstrip()

def solve(a, b):
	counter = 1
	while a != 1 and b != 1:
		if a > b:
			diff = a // b
			a -= b * diff
			counter += diff
		else:
			diff = b // a
			b -= a * diff
			counter += diff
	if a > 1:
		counter += a - 1
	if b > 1:
		counter += b - 1
	return counter

def printOutput(ans):
	sys.stdout.write(str(ans) + '\n')

def readinput():
	(a, b) = getInts()
	printOutput(solve(a, b))
readinput()


from sys import stdin
input = stdin.readline
(a, b) = map(int, input().split())
ans = a // b
while a % b != 0:
	(a, b) = (b, a % b)
	ans += a // b
print(ans)


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


(a, b) = map(int, input().split())
ans = 0
while a and b:
	if a % b == 0 or b % a == 0:
		print(max(a // b, b // a) + ans)
		exit(0)
	if a - b > 0:
		ans += a // b
		(a, b) = (a % b, b)
	else:
		ans += b // a
		(a, b) = (a, b % a)
if a % b == 0:
	ans += a // b
else:
	ans += b // a
print(ans)


import fractions

def resistance():
	(_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 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())

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))


from sys import stdin, stdout, setrecursionlimit
stdin.readline

def mp():
	return list(map(int, stdin.readline().strip().split()))

def it():
	return int(stdin.readline().strip())
from collections import defaultdict as dd, Counter as C, deque
from math import ceil, gcd, sqrt, factorial, log2, floor
from bisect import bisect_right as br, bisect_left as bl
import heapq

def solve(a, b):
	if a == 0:
		return 0
	return b // a + solve(b % a, a)
print(solve(*mp()))


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


from __future__ import print_function
from sys import stdin
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(a, b) = gil()
ans = 0
while min(a, b) != 1:
	(n, d) = (max(a, b), min(a, b))
	ans += n // d
	(a, b) = (n % d, d)
ans += max(a, b)
print(ans)


(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) = map(int, input().split())
ans = 0
while True:
	if a == 0 or b == 0:
		break
	if a <= b:
		ans += b // a
		b = b % a
	elif a > b:
		ans += a // b
		a = a % b
print(ans)


(a, b) = map(int, input().split())
ans = 1
while a != 1 or b != 1:
	if min(a, b) > 1:
		ans += max(a, b) // min(a, b)
	else:
		ans += max(a, b) - 1
	(a, b) = (max(max(a, b) % min(a, b), 1), min(a, b))
print(ans)


(a, b) = map(int, input().split())
ans = 0
c = 1
while a != 1:
	ans += a // b
	(a, b) = (b, a % b)
	c += 1
	if c > 100:
		break
ans += b
print(ans)


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


def euc(a, b):
	if b == 0:
		return 0
	return a // b + euc(b, a % b)
(a, b) = [int(i) for i in input().split()]
print(euc(a, b))


while 1:
	try:
		(a, b) = map(int, input().split())
		res = 0
		while a and b:
			res += a // b
			a %= b
			(a, b) = (b, a)
		print(res)
	except EOFError:
		break


import math as mt
import sys, string
input = sys.stdin.readline
from collections import defaultdict
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())

def fun(a, b):
	if a == 0:
		return 0
	if a == 1:
		return b
	else:
		return b // a + fun(b % a, a)
(a, b) = M()
if a < b:
	print(fun(a, b))
else:
	print(a // b + fun(a % b, b))


def gcd(a, b):
	if b == 0:
		return 0
	return a // b + gcd(b, a % b)
(a, b) = map(int, input().split())
print(gcd(a, b))


def main():
	(a, b) = map(int, input().split())
	ans = 0
	while a != 0:
		ans += a // b
		a = a % b
		if a == 0:
			break
		(a, b) = (b, a)
	print(ans)
main()


import math
(a, b) = map(int, input().split())
if a % b == 0:
	print(int(a / b))
else:
	c = 0
	while b:
		c += a // b
		temp = a
		a = b
		b = temp % b
	print(c)


def check(x, y):
	integer = x // y
	if x == integer * y:
		return integer
	elif x > y:
		result = integer
		x = x % y
		if x == 1:
			result += y
			return result
		elif x != 1:
			result += check(y, x)
			return result
	return check(y, x)
(a, b) = [int(i) for i in input().split()]
print(check(a, b))


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


def fun(a, b):
	if a == 0 or b == 0:
		return 0
	return b // a + fun(b % a, a)
(a, b) = list(map(int, input().split()))
if a <= b:
	print(b // a + fun(b % a, a))
else:
	print(a // b + fun(a % b, b))


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


def answer(a, b):
	count = 0
	while a != 0 and b != 0:
		if a >= b:
			count += a // b
			a = a % b
		else:
			count += b // a
			b = b % a
	return count
(a, b) = map(int, input().split())
print(answer(a, b))


def main():
	(a, b) = [int(i) for i in input().split()]
	i = 1
	while not (a == 1 and b == 1):
		if a < b:
			(a, b) = (b, a)
		k = (a - 1) // b
		i += k
		a -= k * b
	print(i)
main()


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def value():
	return map(int, input().split())

def array():
	return [int(i) for i in input().split()]
(a, b) = value()
ans = 0
while a % b != 0:
	ans += a // b
	a = a % b
	(a, b) = (b, a)
print(ans + a // b)


import sys
import string
import math
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache
from fractions import Fraction

def mi(s):
	return map(int, s.strip().split())

def lmi(s):
	return list(mi(s))

def tmi(s):
	return tuple(mi(s))

def mf(f, s):
	return map(f, s)

def lmf(f, s):
	return list(mf(f, s))

def js(lst):
	return ' '.join((str(d) for d in lst))

def jsns(lst):
	return ''.join((str(d) for d in lst))

def line():
	return sys.stdin.readline().strip()

def linesp():
	return line().split()

def iline():
	return int(line())

def mat(n):
	matr = []
	for _ in range(n):
		matr.append(linesp())
	return matr

def matns(n):
	mat = []
	for _ in range(n):
		mat.append([c for c in line()])
	return mat

def mati(n):
	mat = []
	for _ in range(n):
		mat.append(lmi(line()))
	return mat

def pmat(mat):
	for row in mat:
		print(js(row))

def recb(a, b):
	if a == b:
		return 1
	elif a > b:
		return 1 + rec(a - b, b)
	else:
		return 1 + rec(a, b - a)

def rec(a, b):
	ans = 0
	while True:
		if a == b:
			ans += 1
			break
		elif a == 0 or b == 0:
			break
		if a > b:
			k = (a - a % b) // b
			(a, b) = (a % b, b)
		elif a < b:
			k = (b - b % a) // a
			(a, b) = (a, b % a)
		ans += k
	return ans

def main():
	(a, b) = mi(line())
	print(rec(a, b))
main()


def Euclidian(a, b):
	if a is 0 or b is 0:
		return 0
	if a < b:
		t = a
		a = b
		b = t
	return a // b + Euclidian(b, a % b)
	Euclidian(b, a % b)
(a, b) = map(int, input().split())
print(Euclidian(a, b))


(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 reduce(a, b):
	if a == 1 or b == 1:
		return max(a, b)
	else:
		(a, b) = (b, a)
		return a // b + reduce(a % b, b)
(a, b) = map(int, input().strip().split())
ans = a // b
a %= b
if a != 0:
	ans += reduce(a, b)
print(ans)


from sys import stdin
import math
from collections import defaultdict, deque

def solution(a, b):
	if a == 1:
		return b
	elif b == 1:
		return a
	elif a < b:
		return b // a + solution(b - b // a * a, a)
	else:
		return a // b + solution(a - a // b * b, b)

def one_fraction(num):
	return num
(a, b) = list(map(int, stdin.readline().split()))
print(solution(a, b))