One day Vasya was sitting on a not so interesting Maths lesson and making an origami from a rectangular a mm  ×  b mm sheet of paper (a > b). Usually the first step in making an origami is making a square piece of paper from the rectangular sheet by folding the sheet along the bisector of the right angle, and cutting the excess part.

 [Image] 

After making a paper ship from the square piece, Vasya looked on the remaining (a - b) mm  ×  b mm strip of paper. He got the idea to use this strip of paper in the same way to make an origami, and then use the remainder (if it exists) and so on. At the moment when he is left with a square piece of paper, he will make the last ship from it and stop.

Can you determine how many ships Vasya will make during the lesson?


-----Input-----

The first line of the input contains two integers a, b (1 ≤ b < a ≤ 10^12) — the sizes of the original sheet of paper.


-----Output-----

Print a single integer — the number of ships that Vasya will make.


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

Output
2

Input
10 7

Output
6

Input
1000000000000 1

Output
1000000000000



-----Note-----

Pictures to the first and second sample test.

 [Image]

Difficulty: EASY
Tags: Mathematics

Implementation

Starter code:

Solutions:
S = input().split()
a = int(S[0])
b = int(S[1])
k = 0
ost = 0
while a >= 1 and b >= 1:
	k = k + a // b
	ost = a % b
	a = b
	b = ost
print(k)


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


def gcd(x, y):
	return 0 if y == 0 else x // y + gcd(y, x % y)
(x, y) = list(map(int, input().split()))
print(gcd(x, y))


(a, b) = tuple(map(int, input().split(' ')))
ships = 0
while a != b and a > 0 and (b > 0):
	resp = a // b
	a = a % b
	if b > a:
		(a, b) = (b, a)
	ships += resp
print(ships)


def sp(w, h):
	if w < h:
		(w, h) = (h, w)
	if h == 0:
		return 0
	return w // h + sp(h, w % h)
[a, b] = list(map(int, input().split(' ')))
print(sp(a, b))


numbers = list(map(int, input().split()))
a = numbers[0]
b = numbers[1]
count = 0
while a != 0 and b != 0:
	if a > b:
		count += a // b
		a = a % b
	else:
		count += b // a
		b = b % a
print(count)


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


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


ins = input().split()
a = int(ins[0])
b = int(ins[1])
ans = 0
while b != 0:
	ans += a // b
	a = a % b
	if a < b:
		q = a
		a = b
		b = q
print(ans)


(a, b) = (int(i) for i in input().split())
c = 0
while b > 0:
	c += a // b
	a %= b
	if b > a:
		(a, b) = (b, a)
print(c)


(a, b) = map(int, input().strip().split())
c = 0
while True:
	if a < b:
		(a, b) = (b, a)
	if a % b == 0:
		print(c + a // b)
		break
	if a == b:
		print(c + 1)
		break
	c += a // b
	a = a % b


(a, b) = sorted([int(i) for i in input().split()], reverse=True)
r = 0
while a != 0 and b != 0:
	s = 0
	if a > b:
		s = int(a / b)
		a -= b * s
	else:
		s = int(b / a)
		b -= a * s
	r += s
print(r)


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


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


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


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


import math, fractions

def solve(a, b):
	if a == b:
		return 1
	else:
		tmax = max(a, b)
		tmin = min(a, b)
		if tmin == 1:
			return tmax
		elif tmax % tmin == 0:
			return tmax // tmin
		else:
			return tmax // tmin + solve(tmax % tmin, tmin)
(a, b) = [int(x) for x in input().split()]
print(solve(a, b))


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


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


(a, b) = map(int, input().split())
v = 1
while a != b:
	c = (a - 1) // b
	(a, b, v) = (b, a - b * c, v + c)
print(v)


__author__ = 'ruckus'
(a, b) = map(int, input().split())
n = 0
while a != 0 and b != 0:
	if a > b:
		k = int(a / b)
		a -= k * b
		n += k
	else:
		k = int(b / a)
		b -= k * a
		n += k
print(n)


import unittest
import sys
import os
import argparse
import re
import random
import subprocess
import getpass
import shutil

class Paper:

	def __init__(self, arg_str=''):
		self.arg_str = arg_str
		parser = argparse.ArgumentParser(description='Paper script')
		parser.add_argument('a', nargs='?', default=1, type=int, help='size a')
		parser.add_argument('b', nargs='?', default=1, type=int, help='size b')
		self.args = parser.parse_args(self.arg_str.split())
		self.set_cur_size((self.args.a, self.args.b))

	def set_cur_size(self, size):
		self.cur_size = size
		self.num = 0

	def iterate(self):
		if self.cur_size[0] < self.cur_size[1]:
			self.cur_size = (self.cur_size[1], self.cur_size[0])
		self.num += self.cur_size[0] // self.cur_size[1]
		remainder = self.cur_size[0] % self.cur_size[1]
		self.cur_size = (remainder, self.cur_size[1])
		return 1 if remainder else 0

	def calculate(self, size=None):
		if size is not None:
			self.set_cur_size(size)
		while self.iterate():
			pass
		return self.num

	def run(self, test=False):
		print(self.calculate())
		if test:
			return

def main():
	sb = Paper(input())
	sb.run()

class unitTests(unittest.TestCase):

	def test_Paper_class__basic_functionality(self):
		d = Paper('2 2')
		self.assertEqual(d.args.a, 2)
		self.assertEqual(d.cur_size, (2, 2))
		d.set_cur_size((3, 1))
		self.assertEqual(d.cur_size, (3, 1))
		d.set_cur_size((2, 2))
		self.assertEqual(d.iterate(), 0)
		self.assertEqual(d.num, 1)
		d = Paper()
		d.set_cur_size((10, 3))
		self.assertEqual(d.iterate(), 1)
		self.assertEqual(d.cur_size, (1, 3))
		self.assertEqual(d.num, 3)
		d = Paper()
		d.set_cur_size((10, 3))
		self.assertEqual(d.calculate(), 6)
		self.assertEqual(d.calculate((10, 7)), 6)
		self.assertEqual(d.calculate((1000000000000, 1)), 1000000000000)

	def test_Paper_class__run(self):
		d = Paper('3 2')
		d.run(test=True)
if sys.argv[-1] == '-ut':
	unittest.main(argv=[' '])
main()


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

def solve(x, y):
	if x == 0:
		return 0
	if y < x:
		return solve(y, x)
	if y == x:
		return 1
	sq = y // x
	return sq + solve(x, y - sq * x)
sol = solve(a, b)
print(sol)


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


(a, b) = map(int, input().split())
ans = 0
while True:
	if a % b == 0:
		ans += a // b
		break
	else:
		c = a // b
		l1 = a % b
		a = max(b, l1)
		b = min(b, l1)
		ans += c
print(ans)


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


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

def kor(a, b, k=0):
	if max(a, b) % min(a, b) == 0:
		return k + max(a, b) // min(a, b)
	else:
		k = k + max(a, b) // min(a, b)
		return kor(max(a, b) % min(a, b), min(a, b), k)
print(kor(a, b))


a = list(map(int, input().split()))
c = 0
while max(a) != 0 and max(a) % min(a) != 0:
	c += max(a) // min(a)
	p = max(a) % min(a)
	a = [min(a), p]
if max(a) % min(a) == 0:
	c += max(a) // min(a)
print(c)


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


str = input().split()
a = int(str[0])
b = int(str[1])
x = 0
boat = 0
while a >= 0 or b >= 0:
	if a == 0 or b == 0:
		break
	if a // b > 0:
		this_boat = a // b
		boat += this_boat
		a = a - b * this_boat
	if a == 0:
		break
	if b // a > 0:
		this_boat = b // a
		boat += this_boat
		b = b - a * this_boat
	if b == 0:
		break
print(boat)


(n, m) = map(int, input().split())
ans = 0
while n % m > 0:
	c = n
	d = m
	ans = ans + n // m
	n = max(c % d, d)
	m = min(c % d, d)
print(ans + n // m)


(a, b) = map(int, input().split())
ans = 0
while True:
	if a == 0 or b == 0:
		break
	if a < b:
		(a, b) = (b, a)
	ans += a // b
	a = a % b
print(ans)


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


s = input()
(a, b) = s.split(' ')
(a, b) = (int(a), int(b))
ans = 1
while a != b and a and b:
	if a < b:
		(a, b) = (b, a)
	d = a // b
	if a % b == 0:
		d -= 1
	ans += d
	(a, b) = (b, a - d * b)
print(ans)


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


contador = 0

def dobrar_papel(a, b):
	global contador
	if a <= 0 or b <= 0:
		return None
	if a == b:
		contador = contador + 1
		return None
	elif b > a:
		max_fator = binario(b, a)
		contador = contador + max_fator
		dobrar_papel(a, b - max_fator * a)
	else:
		max_fator = binario(a, b)
		contador += max_fator
		dobrar_papel(a - max_fator * b, b)

def binario(grande, pequeno):
	aux = -1
	limite_superior = grande
	limite_inferior = 1
	while limite_inferior <= limite_superior:
		media = (limite_superior + limite_inferior) // 2
		if media == aux:
			break
		if media * pequeno >= grande:
			limite_superior = media - 1
		elif media * pequeno < grande:
			limite_inferior = media
		aux = media
	return media

def main():
	entrada = input()
	entrada = entrada.split(' ')
	a = int(entrada[0])
	b = int(entrada[1])
	dobrar_papel(a, b)
	print(contador)
main()


from math import *
(a, b) = map(int, input().split())
r = 0
while a > b:
	s = a // b - (a % b == 0)
	r += s
	e = a
	a = b
	b = e - s * b
print(r + 1)


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


(w, h) = map(int, input().split())
turns = 0
while h != w and h != 0 and (w != 0):
	if h > w:
		turns += h // w
		h = h % w
	else:
		turns += w // h
		w = w % h
print(turns)


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


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


def ii():
	return int(input())

def fi():
	return float(input())

def si():
	return input()

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

def li():
	return list(mi())
import math
(a, b) = mi()
c = 0
while a > 0 and b > 0:
	c += a // b
	a = a % b
	(a, b) = (b, a)
print(c)


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


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


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


def main():
	[a, b] = list(map(int, input().split()))
	ans = 0
	while 1:
		if a > b:
			ans += a // b
			if a % b == 0:
				break
			a = a % b
		else:
			ans += b // a
			if b % a == 0:
				break
			b = b % a
	print(ans)
	return

def __starting_point():
	main()
__starting_point()


def how_many_squares(A, B):
	remainder = 0
	if A > B:
		return (A // B, A % B, B)
	elif B > A:
		return (B // A, B % A, A)
	else:
		return (1, 0, 0)
(A, B) = [int(x) for x in input().split()]
total_count = 0
while A != 0 and B != 0:
	(count, A, B) = how_many_squares(A, B)
	total_count += count
print(total_count)


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


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


(x, y) = [int(i) for i in input().split()]
z = 0
while x != 0:
	if x < y:
		(x, y) = (y, x)
	z += x // y
	x = x % y
print(z)


import math
(a, b) = map(int, input().split())
ans = 1
while a != b:
	if a > b:
		ans += math.ceil((a - b) / b)
		a -= b * math.ceil((a - b) / b)
	else:
		ans += math.ceil((b - a) / a)
		b -= a * math.ceil((b - a) / a)
print(ans)


def read_list():
	return [int(i) for i in input().split()]

def new_list(n):
	return [0 for i in range(n)]

def new_matrix(n, m=0):
	return [[0 for i in range(m)] for i in range(n)]
(w, h) = read_list()
c = 0
while min(w, h) > 0:
	if w > h:
		c = c + w // h
		w = w % h
	else:
		c = c + h // w
		h = h % w
print(c)


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


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


(a, b) = map(int, input().split())
sum = 0
while True:
	if a > b:
		sum += a // b
		a -= a // b * b
	else:
		sum += b // a
		b -= b // a * a
	if a == 0 or b == 0:
		break
print(sum)


(a, b) = map(int, input().split())
res = 0
while True:
	if b <= 0 or a <= 0:
		break
	if b == 1:
		res += a
		break
	r = a // b
	res += r
	aux = a
	a = max(a - r * b, b)
	b = min(aux - r * b, b)
print(res)


(a, b) = map(int, input().split())
ans = 0
while True:
	count = max(a, b) // min(a, b)
	help = a
	a = max(a, b) - count * min(a, b)
	b = min(help, b)
	ans += count
	if a == b or a == 0:
		break
print(ans)


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


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


inp = input()
inp = inp.split()
a = int(inp[0])
b = int(inp[1])
ans = 0
while b > 0:
	ans += a // b
	c = a % b
	a = b
	b = c
print(ans)


__author__ = '(Lambdell)'

def solve(a, b):
	(a, b) = (max(a, b), min(a, b))
	if a % b == 0:
		return a // b
	else:
		return solve(a % b, b) + a // b
(a, b) = map(int, input().strip().split())
print(solve(a, b))


[a, b] = list(map(int, input().rstrip().split()))
tik = 0
while a:
	if a < b:
		(a, b) = (b, a)
	tik += a // b
	a = a % b
print(tik)


class CodeforcesTask527ASolution:

	def __init__(self):
		self.result = ''
		self.dims = []

	def read_input(self):
		self.dims = [int(x) for x in input().split(' ')]

	def process_task(self):
		i = 0
		a = self.dims[0]
		b = self.dims[1]
		while a != b:
			if a % b:
				i += a // b
				a = a % b
				if a < b:
					swap = a
					a = b
					b = swap
			else:
				i += a // b
				break
		self.result = str(i)

	def get_result(self):
		return self.result
Solution = CodeforcesTask527ASolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


(a, b) = map(int, input().split())
count = 0
while a > 0 and b > 0:
	if a >= b:
		(cnt, a) = divmod(a, b)
		count += cnt
	else:
		(cnt, b) = divmod(b, a)
		count += cnt
print(count)


(a, b) = [int(i) for i in input().split()]

def remains(a, b):
	(a, b) = (max(a, b), min(a, b))
	return (a // b, a % b, b)
total = 0
while min(a, b) > 0:
	(s, a, b) = remains(a, b)
	total += s
print(total)


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


(a, b) = input().split()
(a, b) = (int(a), int(b))
n = 0
count = 0
while a != 1 and b != 1:
	if a == b:
		n = 1
		count = count + 1
		break
	elif a > b:
		count = count + int(a / b)
		a = a % b
		if a == 0:
			break
	elif a < b:
		count = count + int(b / a)
		b = b % a
		if b == 0:
			break
if n == 1:
	print(count)
else:
	print(count + a * b)


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

def f(a, b):
	if a == b:
		return 1
	elif a == 0 or b == 0:
		return 0
	else:
		return a // b + f(max(a - b * (a // b), b), min(a - b * (a // b), b))
print(f(a, b))


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


from copy import copy
(a, b) = map(int, input().split())
cnt = 0
while a > 0 and b > 0:
	na = copy(b)
	cnt += a // b
	nb = a % b
	a = max(na, nb)
	b = min(na, nb)
print(cnt)


import sys
import math
from collections import *

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

def get_list():
	return list(get_ints())

def printspx(*args):
	return print(*args, end='')

def printsp(*args):
	return print(*args, end=' ')
UGLYMOD = int(1000000000.0 + 7)
SEXYMOD = 998244353
MAXN = int(100000.0)
(a, b) = get_ints()
(a, b, ans) = (max(a, b), min(a, b), 0)
while b:
	ans += a // b
	a = a % b
	(a, b) = (max(a, b), min(a, b))
print(ans)


import math
v = [int(i) for i in input().split()]
a = v[0]
b = v[1]
n = 0
while a > 0 and b > 0:
	if a >= b:
		t = int(math.floor(a / b))
		a = a - t * b
		n += t
	else:
		t = int(math.floor(b / a))
		b = b - t * a
		n += t
print(n)


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


def c(a, b):
	return a and b and b // a + c(b % a, a)
(a, b) = [int(x) for x in input().split()]
print(c(a, b))


(a, b) = map(int, input().split())
if a == b:
	print('1')
	exit(0)
count = 0
while a != b:
	if a > b:
		count += int(a / b)
		a = a % b
	elif b > a:
		count += int(b / a)
		b = b % a
	if a == 0 or b == 0:
		break
print(count)


ab = [int(x) for x in input().split()]
a = ab[0]
b = ab[1]
count = 0
while a != b and a != 0 and (b != 0):
	if a > b:
		count += int(a / b)
		a -= b * int(a / b)
	else:
		count += int(b / a)
		b -= a * int(b / a)
if a == b:
	count += 1
print(count)


raw = str(input()).split()
a = int(raw[0])
b = int(raw[1])
c = 0
while a != 0 and b != 0:
	if a > b:
		c += int(a / b)
		a = a % b
	else:
		c += int(b / a)
		b = b % a
print(c)


(a, b) = map(int, input().split())
c = 0
p = 1
while p == 1:
	if a > b:
		if a % b == 0:
			c += a // b
			break
		else:
			c += a // b
			a = a % b
	elif b % a == 0:
		c += b // a
		break
	else:
		c += b // a
		b = b % a
print(c)


(x, y) = map(int, input().split())
count1 = 0
while min(x, y) > 0:
	(x, y) = (max(x, y), min(x, y))
	count1 += x // y
	x = x % y
print(count1)


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

def origami(a, b):
	count = 0
	while a > 0 and b > 0:
		(a, b) = (max(a, b), min(a, b))
		count += a // b
		a = a % b
	return count
print(origami(a, b))


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


(a, b) = [int(i) for i in input().split()]
num_squares = 0
while 1:
	num_squares += a // b
	remainder = a % b
	a = b
	b = remainder
	if a == b or a == 0 or b == 0:
		break
print(num_squares)


(a, b) = map(int, input().split())
ans = 0
if b > a:
	tmp = a
	a = b
	b = tmp
total = a * b
while b != 0:
	qua = b * b
	s = int(total / qua)
	ans += s
	total = total - s * qua
	a = a - s * b
	tmp = a
	a = b
	b = tmp
print(ans)


(a, b) = [int(i) for i in input().split()]
c = 0
k = max(a, b)
l = min(a, b)
while k % l != 0:
	c += k // l
	(k, l) = (l, k % l)
c += k // l
print(c)


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


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


import math

def ships(a, b):
	if a < b:
		return ships(b, a)
	elif a == b:
		return 1
	else:
		return math.ceil(a / b - 1) + ships(a - b * math.ceil(a / b - 1), b)
x = [int(i) for i in input().split(' ')]
print(ships(x[0], x[1]))


def main():
	(a, b) = list(map(int, input().split()))
	count = 0
	mx = max(a, b)
	while a:
		if a < b:
			(a, b) = (b, a)
		less = a // b
		count += less
		a -= b * less
	print(count)

def __starting_point():
	main()
__starting_point()


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

def put(a, b):
	global s
	s += a // b
	l = a % b
	if l != 0:
		put(b, l)
put(a, b)
print(s)


from collections import defaultdict as dd
from collections import Counter as ccd
from itertools import permutations as pp
from itertools import combinations as cc
from random import randint as rd
from bisect import bisect_left as bl
from bisect import bisect_right as br
import heapq as hq
import math
mod = pow(10, 9) + 7

def inp(flag=0):
	if flag == 0:
		return list(map(int, input().strip().split(' ')))
	else:
		return int(input())
(a, b) = inp()
ships = 0
while a > 0 and b > 0:
	if a >= b:
		ships += a // b
		a = a % b
	else:
		ships += b // a
		b = b % a
print(ships)


(a, b) = [int(i) for i in input().split()]
count = 0
while a and b:
	if a > b:
		(n, a) = divmod(a, b)
	else:
		(n, b) = divmod(b, a)
	count += n
print(count)


(a, b) = [int(s) for s in input().split(' ')]
res = 0
while a * b > 0:
	res += a // b
	a %= b
	(a, b) = (b, a)
print(res)


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


import math
num = input()
numlista = []
numlista = num.split(' ')
if int(numlista[0]) >= int(numlista[1]):
	maior = int(numlista[0])
	menor = int(numlista[1])
else:
	maior = int(numlista[1])
	menor = int(numlista[0])
resposta = 0
counter = 0
while counter == 0:
	if maior % menor == 0:
		resposta += maior / menor
		counter = 1
	else:
		x = maior - math.floor(maior / menor) * menor
		resposta += math.floor(maior / menor)
		maior = menor
		menor = x
print(int(resposta))


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


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


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


(a, b) = input().split()
a = int(a)
b = int(b)
l = 0
(x, y) = (a, b)
while 1:
	if x == y:
		print(l + 1)
		break
	else:
		if x < y:
			(x, y) = (y, x)
		l += x // y
		if x % y != 0:
			x = x - x // y * y
		else:
			print(l)
			break


(a, b) = map(int, input().split())
cn = 0
while True:
	if a % b != 0:
		d = a % b
		c = a // b
		cn += c
		(a, b) = (b, d)
	else:
		cn += a / b
		break
print(int(cn))


(a, b) = map(int, input().split())
m = max(a, b)
n = min(a, b)
t = 0
while m > 1 and n > 1:
	if m == n:
		break
	t += m // n
	c = m % n
	m = n
	n = c
if n == 1:
	t += m
print(t)


(x, y) = map(int, input().split())
s = x // y
r = x % y
while r != 0:
	x = y
	y = r
	s = s + x // y
	r = x % y
print(s)


(a, b) = map(int, input().split())
if a % b == 0:
	print(a // b)
else:
	count = a // b + 1
	(a, b) = (max(a - b * (a // b), b), min(a - b * (a // b), b))
	while a != b:
		(a, b) = (max(a - b, b), min(a - b, b))
		if a % b == 0:
			break
		count += 1
	print(count + a // b)


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


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


import sys
import math
import bisect

def solve(a, b):
	ans = 0
	while a and b:
		(a, b) = (min(a, b), max(a, b))
		ans += b // a
		b %= a
	return ans

def main():
	(a, b) = map(int, input().split())
	ans = solve(a, b)
	print(ans)
main()


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


count = 0
(a, b) = list(map(int, input().split(' ')))
while a > 0 and b > 0:
	count += a // b
	x = b
	b = a % b
	a = x
print(count)


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


def gcd(x, y):
	counter = 0
	while y != 0:
		counter += x // y
		(x, y) = (y, x % y)
	return counter
(x, y) = map(int, input().split())
print(gcd(x, y))


total = 0

def origami(a, b):
	global total
	if a % b == 0:
		total += int(a / b)
		return False
	elif a / b > 1:
		total += int((a - a % b) / b)
		origami(max(b, a % b), min(b, a % b))
	else:
		total += 1
		origami(max(b, a - b), min(b, a - b))
(a, b) = map(int, input().split())
origami(a, b)
print(total)


def fun(a, b):
	cnt = 0
	while True:
		cnt += a // b
		tmp = a
		a = b
		b = tmp % b
		if b == 0:
			break
	return cnt
(a, b) = [int(c) for c in input().split()]
print(fun(a, b))


text = [int(i) for i in input().split(' ')]
a = text[0]
b = text[1]
n = 0
while a != b and b > 0:
	n += a // b
	t = a
	a = b
	b = t - t // b * b
	if a < b:
		t = a
		a = b
		b = t
print(n)


(a, b) = map(int, input().split())
ret = 0
while 1:
	if b == 0:
		break
	ret += a // b
	(a, b) = (max(b, a % b), min(b, a % b))
print(ret)


def f(a, b):
	if a == b:
		return 1
	if b == 1:
		return a
	if a <= 0 or b <= 0:
		return 0
	r = 0
	while a > 0 and b > 0:
		if a >= b:
			r += a // b
			a = a % b
		else:
			r += b // a
			b = b % a
	return r

def main():
	return f(*list(map(int, input().split(' '))))
print(main())


counter = 0
(a, b) = [int(i) for i in input().split()]
while 1:
	if a > b:
		counter += int(a / b)
		a = a % b
		if a == 0:
			break
	elif b > a:
		counter += int(b / a)
		b = b % a
		if b == 0:
			break
	else:
		counter += 1
		break
print(counter)


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


string = input().split()
a = int(string[0])
b = int(string[1])
count = 0
while a != 0 and b != 0:
	if a > b:
		lastA = a
		count = count + int(a / b)
		a = b
		b = lastA % b
	else:
		lastB = b
		count = count + int(b / a)
		b = a
		a = lastB % a
print(count)


import sys, math
for line in sys.stdin:
	a = []
	for word in line.split():
		a.append(int(word))
	mayor = max(a[0], a[1])
	menor = min(a[0], a[1])
	cont = 0
	flag = 0
	while mayor != 1 and menor != 1:
		res = mayor % menor
		res1 = int(mayor / menor)
		cont += res1
		mayor = menor
		menor = res
		if mayor == 0 or menor == 0:
			flag = 1
			break
	if flag == 1:
		print(str(cont))
	else:
		cont += mayor
		print(str(cont))


Count = 0
(A, B) = map(int, input().split())
while 0 not in [A, B]:
	(A, B) = (max(A, B), min(A, B))
	if B <= A - B:
		Count += A // B
		A = A % B
	else:
		A = A - B
		Count += 1
print(Count)


def main():
	(A, B) = input().split()
	A = int(A)
	B = int(B)
	qtd = 0
	while A != 0 and B != 0:
		if A > B:
			qtd += A // B
			A %= B
		else:
			qtd += B // A
			B %= A
	print(qtd)
main()


(a, b) = map(int, input().split(' '))
result = 0
while True:
	if a == 0 or b == 0:
		break
	elif a <= b:
		result += b // a
		b = b % a
	else:
		result += a // b
		a = a % b
print(result)


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


import math
L = list(map(int, input().split()))
C = 0
L.sort()
while L[0] != L[1]:
	try:
		New = int(math.floor(L[1] / L[0]))
	except:
		break
	L[1] = L[1] - New * L[0]
	C += New
	L.sort()
print(C)


(a, b) = [int(x) for x in input().split()]
pieces = int(a / b)
a -= b * pieces
c = a
while c != 0:
	a = b
	b = c
	pieces += int(a / b)
	c = a % b
print(pieces)


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


def main():
	(a, b) = (int(i) for i in input().split())
	n = 0
	while a % b:
		n += a // b
		(a, b) = (b, a % b)
	n += a // b
	print(n)
main()


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


f = lambda : input()
(a, b) = map(int, f().split())
c = 0
while a != b and a != 0 and (b != 0):
	lo = min(a, b)
	hi = max(a, b)
	a = hi % lo
	b = lo
	c += int(hi / lo)
print(c)


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


(a, b) = [int(i) for i in input().split()]
(a, b) = (min(a, b), max(a, b))
result = 0
while a != b:
	(a, b) = (min(a, b), max(a, b))
	result += (b - 1) // a
	b -= (b - 1) // a * a
print(result + 1)


(n, m) = map(int, input().strip().split())
k = 0
while n != 0 and m != 0:
	if n > m:
		k += int(n / m)
		n = n % m
	else:
		k += int(m / n)
		m = m % n
print(k)


import sys
import math
(a, b) = [int(x) for x in sys.stdin.readline().split()]
res = 0
while True:
	v = int(a / b)
	k = a % b
	res += v
	if k == 0:
		print(res)
		exit()
	else:
		a = b
		b = k


def foldtimes(a, b):
	count = 0
	while a != b:
		if a < b:
			if a == 1:
				return b + count
			foldtimes = b // a
			leftover = b % a
			b = leftover
			count = count + foldtimes
			if leftover == 0:
				return count
		else:
			if b == 1:
				return a + count
			foldtimes = a // b
			leftover = a % b
			a = leftover
			count = count + foldtimes
			if leftover == 0:
				return count
	return count
listone = input().split()
a = int(listone[0])
b = int(listone[1])
print(foldtimes(a, b))


(a, b) = map(int, input().split())
n = 1
while a != b and a != 0 and (b != 0):
	if b > a:
		x = b
		b = a
		a = x
	n += a // b
	a = abs(a - a // b * b)
print(n - 1)


def paper(a, b):
	num = 0
	(a, b) = (a, b) if a > b else (b, a)
	while True:
		increase = a // b
		num += increase
		temp = b
		b = a % b
		a = temp
		if b == 0:
			break
	return num
input_str = [int(p.strip()) for p in input().split(' ') if p != '']
print(paper(input_str[0], input_str[1]))


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


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


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

def __starting_point():
	main()
__starting_point()


(a, b) = map(int, input().split())
i = 0
while a != b:
	if a < b:
		tmp = a
		a = b
		b = tmp
	i += int(a / b)
	if a % b != 0:
		a -= int(a / b) * b
	else:
		a = b
		i -= 1
	if a < 1:
		a = 1
		i -= 1
o = i + 1
print(o)


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


s = input().split()
for i in range(2):
	s[i] = int(s[i])
s = sorted(s)
a = int(s[1])
b = int(s[0])
res = 1
hooks = int(1)
if a % b == 0:
	print(int(a / b))
	hooks = int(2)
else:
	while True:
		if a % 2 == 0 and b % 2 == 0:
			a = int(a / 2)
			b = int(b / 2)
		else:
			break
	if a > b ** 2:
		res += a // b
		(a, b) = (max(b, a - b * (a // b)), min(b, a - b * (a // b)))
	while a != b and a > 0 and (b > 0):
		(a, b) = (max(b, a - b), min(b, a - b))
		if a % b == 0:
			res += int(a / b)
			print(res)
			hooks = int(2)
			break
		res += 1
if hooks == 1:
	print(res)


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


v = [int(i) for i in input().split()]
a = min(v)
b = max(v)
c = 0
while a != b and (a != 0 and b != 0):
	c += b // a
	b = b % a
	(b, a) = (max(a, b), min(a, b))
print(c)


def cortar_quadrados(a, b):
	if a > b and b > 0:
		return a // b + cortar_quadrados(b, a % b)
	return 0
paper = [int(x) for x in input().split()]
res = cortar_quadrados(paper[0], paper[1])
print(res)


def gcd(pair):
	(a, b) = pair
	answer = 0
	while b != 0:
		answer += a // b
		(a, b) = (b, a % b)
	return answer
print(gcd([int(next) for next in input().split()]))


s = [int(n) for n in input().split()]
a = max(s)
b = min(s)
if a % b == 0:
	print(a // b)
else:
	l = 0
	while 1:
		l += a // b
		d = a % b
		g = b
		h = d
		a = max(g, h)
		b = min(g, h)
		if d == 0:
			break
	print(l)


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


def f(a, b, c):
	return f(b, a % b, c + a // b) if b else c
a = list(map(int, input().split()))
print(f(a[0], a[1], 0))


(a, b) = input().split()
a = int(a)
b = int(b)
i = 0
while a != b:
	if a % b == 0:
		i = i + a / b
		break
	else:
		i = i + a // b
		c = b
		b = a % b
		a = c
print(int(i))


(n, m) = map(int, input().rstrip().split(' '))
c = 0
while n * m != 0:
	if n < m:
		(n, m) = (m, n)
	c += n // m
	n = n % m
print(c)


(n, m) = [int(x) for x in input().split()]
(c, mn, mx) = (0, 0, 0)
while n != m and n > 0 and (m > 0):
	p = max(n, m) // min(n, m)
	c += p
	if n > m:
		n -= p * m
	else:
		m -= p * n
print(c)


dim = list(map(int, input().split(' ')))
length = dim[0]
breadth = dim[1]
no_of_ships = 0
while length - breadth > 0:
	no_of_ships += length // breadth
	length -= breadth * (length // breadth)
	if length > 0 and length < breadth:
		temp = breadth
		breadth = length
		length = temp
print(no_of_ships)


a_b = input().split()
a = int(a_b[0])
b = int(a_b[1])
if a > b:
	bolshoe = a
	menshee = b
else:
	bolshoe = b
	menshee = a
vivod = 1
x = 0
i = 0
if bolshoe == menshee:
	x = 1
elif a == 1 and b != 1:
	vivod = b
	x = 1
elif b == 1 and a != 1:
	vivod = a
	x = 1
while i > -1:
	if x == 1:
		print(vivod)
		break
	if (bolshoe - menshee) % menshee > 0:
		vivod = vivod + bolshoe // menshee
		bolshoe = bolshoe - menshee * (bolshoe // menshee)
	else:
		vivod = vivod + (bolshoe - menshee) / menshee
		bolshoe = bolshoe - menshee * (bolshoe - menshee) / menshee
	if bolshoe < menshee:
		(bolshoe, menshee) = (menshee, bolshoe)
	if bolshoe == menshee:
		print(int(vivod))
		break
	i += 1


(a, b) = map(int, input().split())
res = 0
while a != b:
	if a > b:
		if b == 0:
			break
		res += a // b
		a -= a // b * b
	elif b > a:
		if a == 0:
			break
		res += b // a
		b -= b // a * a
print(res)


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


(a, b) = [int(i) for i in input().split()]
count = 0
while min(a, b) != 0:
	count += a // b
	(a, b) = (max(b, a % b), min(b, a % b))
print(count)


(a, b) = map(int, input().split())
c = 0
while not 0 in [a, b]:
	if b > a:
		(b, a) = (a, b)
	(c, a) = (c + a // b, a % b)
print(c)


(a, b) = (int(x) for x in input().split())
k = 0
while a != b and a > 0 and (b > 0):
	k += a // b
	(a, b) = reversed(sorted((b, a % b)))
print(k)


R = lambda : list(map(int, input().split()))
(a, b) = R()
x = 1
while a != b:
	if a > 2 * b:
		w = a // b
		if a % b == 0:
			w -= 1
		x += w
		a -= b * w
	else:
		a -= b
		x += 1
	if a < b:
		y = a
		a = b
		b = y
print(x)


import sys
(a, b) = [int(i) for i in input().split(' ')]
a2 = max([a, b])
b2 = min([a, b])
summa = 0
while a2 != 0 and b2 != 0:
	summa += int(a2 / b2)
	b = a2 % b2
	a = b2
	a2 = a
	b2 = b
print(summa)


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


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


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


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 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
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 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) = (max(a, b), min(a, b))
	count = 0
	while a > 0 and b > 0:
		count += a // b
		a = a % b
		(a, b) = (b, a)
	print(count)
for _ in range(1):
	solve()


(a, b) = map(int, input().split())
squares = 0
while True:
	squares += a // b
	a %= b
	if a == 0:
		break
	(a, b) = (b, a)
print(squares)


(a, b) = input().split(' ')
a = int(a)
b = int(b)
i = 0
while 1:
	x = max(a, b)
	y = min(a, b)
	if x % y == 0:
		print(int(x / y) + i)
		break
	else:
		i += int(x / y)
		x = x % y
	a = x
	b = y


import unittest
import random
import time

def solve(a, b):
	count = 0
	if b > a:
		(a, b) = (b, a)
	while True:
		if a == b:
			return count + 1
		if a % b == 0:
			return count + int(a / b)
		n = a // b
		count += n
		a = a % b
		if b > a:
			(a, b) = (b, a)
	return count

def solve_simple(a, b):
	if b > a:
		(a, b) = (b, a)
	if a == b:
		return 1
	a -= b
	return 1 + solve(a, b)

class Test_solution(unittest.TestCase):

	def test_case(self):
		self.assertEqual(solve(2, 2), 1)
		self.assertEqual(solve(2, 1), 2)
		self.assertEqual(solve(10, 7), 6)
		self.assertEqual(solve(1000000000000, 1), 1000000000000)

	def test_random(self):
		for _ in range(1000000):
			a = random.randint(1, 10 ** 12)
			b = random.randint(1, 10 ** 12)
			if b > a:
				(a, b) = (b, a)
			try:
				t = time.time()
				actual = solve(a, b)
				if time.time() - t > 1:
					print(a, b, time.time() - t)
			except RuntimeError as e:
				print('Error on ', a, b, expected, e)
(a, b) = map(int, input().split())
print(solve(a, b))


import sys
(n, m) = list(map(int, input().split(' ')))
answer = 0
if n == 1 or m == 1:
	print(n * m)
	return
while n > 0 and m > 0:
	if n > m:
		answer += int(n / m)
		n %= m
	else:
		answer += int(m / n)
		m %= n
print(answer)


import math, os, sys
import string, re
import itertools, functools, operator
from collections import Counter

def inputint():
	return int(input())

def inputarray(func=int):
	return map(func, input().split())
(a, b) = inputarray()

def ans(a, b):
	if a == b:
		return 1
	elif b == 0:
		return 0
	else:
		return a // b + ans(b, a % b)
print(ans(a, b))


(a, b) = map(int, input().split())
step = 0
while a > b:
	x = (a - 1) // b
	step += x
	(a, b) = (max(a - b * x, b), min(a - b * x, b))
print(step + 1)


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


def f(l):
	(a, b) = l
	c = 0
	while b > 0:
		c += a // b
		t = b
		b = a % b
		a = t
	return c
l = list(map(int, input().split()))
print(f(l))


string = input()
lengths = string.split(' ')
a = int(lengths[0])
b = int(lengths[1])
ships = 0
while b != 0:
	if a < b:
		(a, b) = (b, a)
	ships += a // b
	(a, b) = (b, a - b * (a // b))
print(ships)


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


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


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


(a, b) = list(map(int, input().split()))
ans = 0
while a != b:
	if a < b:
		(a, b) = (b, a)
	ans += (a - 1) // b
	a -= (a - 1) // b * b
print(ans + 1)


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


(a, b) = map(int, input().split())
boats = 0
while b:
	(x, y) = divmod(a, b)
	(a, b, boats) = (b, y, boats + x)
print(boats)


def solve(a, b):
	if a * b == 0:
		return 0
	(count, a) = divmod(a, b)
	return count + solve(b, a)
(a, b) = map(int, input().split())
print(solve(a, b))


import sys
input = sys.stdin.readline
import queue
(n, m) = map(int, input().split())
c = 0
while n != m and n != 0 and (m != 0):
	a = max(n, m)
	b = min(n, m)
	co = a // b
	c += co
	n = a - b * co
	m = b
print(c)


import math
(a, b) = map(int, input().split(' '))
c = 0
r = 1
while r != 0:
	c = c + math.floor(a / b)
	r = a % b
	a = b
	b = r
print(c)


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


A = input()
A = list(map(int, A.split(' ')))
a = A[0]
b = A[1]
cont = 0
while a != b:
	mini = min(a, b)
	maxi = max(a, b)
	cont = cont + maxi // mini
	a = mini
	b = maxi % mini
	if b == 0:
		break
if b != 0:
	cont = cont + 1
print(cont)


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


def lsn():
	global a, b, k
	k += a // b
	a = a - a // b * b
	(a, b) = (max(a, b), min(a, b))
(a, b) = input().split()
a = int(a)
b = int(b)
k = 0
while a > 0 and b > 0:
	lsn()
print(k)


inf = list(map(int, input().split()))
a = inf[0]
b = inf[1]
n = 0
while a != b:
	x = max(a, b)
	y = min(a, b)
	if x % y == 0:
		n = n + int(x / y)
		break
	else:
		(a, b) = (x % y, y)
		n += int(x / y)
print(n)


a = input('').split(' ')
b = int(a[0])
c = int(a[1])
ans = 0
while b != 0 and c != 0:
	e = max(b, c)
	f = min(b, c)
	ans = ans + int(e / f)
	e = e - int(e / f) * f
	b = e
	c = f
print(ans)


def solver(a, b):
	resp = 0
	while b != 0:
		resp += a // b
		aux = a
		a = b
		b = aux % b
	return resp
(a, b) = list(map(int, input().split()))
print(solver(a, b))


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


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


def calc(x, y, ans=0):
	return ans if y == 0 else calc(y, x % y, ans + x // y)
(a, b) = map(int, input().split())
print(calc(a, b))


(a, b) = str(input()).split()
a = int(a)
b = int(b)
value = 0
while True:
	if a % b == 0:
		value += int(a / b)
		break
	value += int(a / b)
	c = a
	a = b
	b = c % b
print(value)


s = input()
(a, b) = [int(x) for x in s.split()]
(c, ans) = (0, 0)
while True:
	c = min(a, b)
	a = max(a, b)
	b = c
	ans += a // b
	a = a % b
	if a % b == 0:
		break
print(ans)


def nori(a, b):
	if a % b == 0:
		return int(a / b)
	s = 0
	res = a % b
	while res != 0:
		d = int(a / b)
		res = a % b
		if res > b:
			a = res
			b = b
		elif b > res:
			a = b
			b = res
		s += d
	return s
a = input().split()
a = [int(a[i]) for i in range(len(a))]
print(nori(a[0], a[1]))


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

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

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	(a, b) = LI()
	if a > b:
		(a, b) = (b, a)
	r = 0
	while a > 0:
		r += b // a
		(a, b) = (b % a, a)
	return r
print(main())


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


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


__author__ = 'myduomilia'
(a, b) = list(map(int, input().split()))
ans = 0
while a * b > 0:
	if a > b:
		ans += a // b
		a = a % b
	else:
		ans += b // a
		b = b % a
print(ans)


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


import sys
(a, b) = map(int, input().split())
if a < b:
	sys.exit(0)
result = 0
while b > 0:
	result += a // b
	a %= b
	if a < b:
		(a, b) = (b, a)
print(result)


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


def main():
	(x, y) = map(int, input().split())
	squares = 0
	while x != 0 and y != 0:
		if x < y:
			squares += y // x
			y -= y // x * x
		else:
			squares += x // y
			x -= x // y * y
	print(squares)
main()


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


(a, b) = [int(x) for x in input().split()]
res = 0
while a != b:
	if a % b == 0:
		res += int(a / b)
		break
	n = int(a // b)
	res += n
	atemp = a
	btemp = b
	a = btemp
	b = atemp - n * btemp
k = int(2 // 1)
print(res)


(a, b) = input().split(' ')
a = int(a)
b = int(b)
s = 0
c = 0
while a != b:
	if not (a == 0 or b == 0):
		if a > b:
			c = a // b
			a %= b
		else:
			c = b // a
			b %= a
		s += c
	else:
		break
print(s)


(a, b) = sorted(map(int, input().split()))
(A, B) = (a, b)
ships = 0
while 0 < a < b:
	ships += b // a
	(a, b) = sorted([b % a, a])
print(ships)


(width, lenght) = map(int, input().split())
ships = 0
while width != lenght and width * lenght != 0:
	if lenght > width:
		ships += lenght // width
		lenght %= width
	else:
		ships += width // lenght
		width %= lenght
print(ships)


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


(a, b) = map(int, input().split())
steps = 0
while a != b and b > 0:
	div = a // b
	a -= b * div
	(a, b) = (max(b, a), min(b, a))
	steps += div
print(steps)


(a, b) = [int(elem) for elem in input().split()]
count = 0
temp = 0
while a and b:
	if a > b:
		temp = a % b
		a //= b
		count += a
		a = temp
	else:
		temp = b % a
		b //= a
		count += b
		b = temp
print(count)


(a, b) = map(int, input().split())
ans = 0
while a > b:
	ans = ans + a // b
	c = b
	b = a - a // b * b
	a = c
	if b == 0:
		break
print(ans)


import math
from decimal import *
getcontext().prec = 30
(a, b) = map(int, input().split())
ans = 0

def fn():
	global a, b
	if a < b:
		(a, b) = (b, a)
	if (a - b) % b == 0:
		x = (a - b) // b
		a -= a
		b -= b
		return x + 1
	x = math.ceil((a - b) / b)
	a -= x * b
	return x
while a * b:
	ans += fn()
print(ans)


(n, m) = map(int, input().split())
l = 0
if n % m != 0:
	while True:
		if n > m:
			if n % m == 0:
				break
			else:
				t = n % m
				l += n // m
				n = t
		elif n < m:
			if m % n == 0:
				break
			else:
				z = m % n
				l += m // n
				m = z
	if n % m == 0:
		print(l + n // m)
	elif m % n == 0:
		print(l + m // n)
else:
	print(n // m)


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


(a, b) = map(int, input().split())
c = 0
while True:
	if a == b:
		c += 1
		break
	elif b == 1:
		c += a
		break
	elif a % b == 0:
		c += a // b
		break
	else:
		c += a // b
		t = b
		b = a % b
		a = t
print(c)


import operator as op
import re
import sys
from bisect import bisect, bisect_left, insort, insort_left
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from functools import reduce
from itertools import accumulate, combinations, combinations_with_replacement, groupby, permutations, product
from math import acos, asin, atan, ceil, cos, degrees, factorial, gcd, hypot, log2, pi, radians, sin, sqrt, tan
from operator import itemgetter, mul
from string import ascii_lowercase, ascii_uppercase, digits

def inp():
	return int(input())

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

def instr():
	s = input()
	return list(s[:len(s)])

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

def def_value():
	return 0

def e_gcd(a, b, res):
	if a == b or b == 0:
		return res
	res += a // b
	return e_gcd(b, a % b, res)
(a, b) = invr()
res = e_gcd(a, b, 0)
print(res)


def solve(a, b):
	cnt = 0
	while b > 0:
		cnt += a // b
		(a, b) = (b, a % b)
	return cnt

def main():
	[a, b] = [int(i) for i in input().strip().split()]
	result = solve(a, b)
	print(result)
main()


import math
entradas = input()
lista = entradas.split()
a = int(lista[0])
b = int(lista[1])
resultado = 0
while a > 0 and b > 0:
	if a >= b:
		resultado += a // b
		a = a % b
	else:
		resultado += b // a
		b = b % a
print(resultado)


(a, b) = [int(i) for i in input().split()]
if a % b == 0:
	res = a // b
elif b % a == 0:
	res = b // a
else:
	res = 0
	while a != b:
		(a, b) = (max(a, b), min(a, b))
		res += a // b
		if a % b == 0:
			break
		else:
			(a, b) = (b, a % b)
	else:
		res += 1
print(res)


(x, y) = map(int, input().split())
output = 0
while min(x, y) != 0:
	r = x // y
	output += r
	x -= r * y
	(x, y) = (max(x, y), min(x, y))
print(output)


import math as m

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

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


(c, d) = map(int, input().split())
count = 0
count = c // d
a = d
b = c % d
while c % d != 0:
	if b <= 1:
		count += a
		break
	elif b > 0 and a % b == 0:
		count += a // b
		break
	elif a == b:
		break
	else:
		count += 1
		c = b
		b = a - b
		a = c
		if b > a:
			(a, b) = (b, a)
print(count)


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys

def cal(a, b):
	if a < b:
		return cal(b, a)
	if a == b:
		return 1
	if a == 0 or b == 0:
		return 0
	k = a // b
	return k + cal(b, a - k * b)
(a, b) = map(int, input().split())
print(cal(a, b))


def main() -> object:
	(a, b) = map(int, input().split())
	res = 0
	while b > 0:
		res += int(a / b)
		tmp = a % b
		a = b
		b = tmp
	return res
print(main())


(a, b) = map(int, input().split())
s = 0
while b > 0:
	i = a // b
	m = b
	b = a - b * i
	a = m
	s += i
print(s)


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


import os
(x, y) = input().split()
x = int(x)
y = int(y)
ans = 0
while x > 0 and y > 0:
	if x > y:
		ans += int(x / y)
		x = x % y
	else:
		ans += int(y / x)
		y = y % x
print(ans)


l = input()
l = l.split()
a = int(l[0])
b = int(l[1])
if min(a, b) == 1:
	print(max(a, b))
else:
	s = 0
	while min(a, b) > 0:
		if min(a, b) == 1:
			s += max(a, b)
			break
		elif a >= b:
			s += a // b
			a = a % b
		else:
			s += b // a
			b = b % a
	print(s)


s = input()
s = s.split()
a = int(s[0])
b = int(s[1])
count = 0
while a > 1 and b > 1:
	count += a // b
	(a, b) = (b, a % b)
if a != 0 and b != 0:
	count += a
print(count)


(a, b) = map(int, input().split())
r = 0
while a > 0 and b > 0:
	if a < b:
		(a, b) = (b, a)
	n = a // b
	a -= n * b
	r += n
print(r)


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


(a, b) = [int(i) for i in input().split()]
i = 0
while True:
	if b == 0:
		break
	else:
		i += a // b
		(a, b) = (b, a % b)
print(i)


(a, b) = list((int(x) for x in input().split()))
if a < b:
	(a, b) = (b, a)
k = 0
while a != 0 and b != 0:
	k += a // b
	a = a % b
	(a, b) = (b, a)
print(k)


(a, b) = map(int, input().split())
num = 0
while a * b != 0:
	(a, b) = sorted([a, b])
	num += b // a
	b = b % a
print(int(num))


import sys
(a, b) = input().split()
(x, y) = (a, b)
c = 0
(a, b) = (int(x), int(y))
if b == 1:
	print(a)
	sys.exit()
while a > 0 and b > 0:
	if a > b:
		c += int(a / b)
		a = int(a % b)
	else:
		c += int(b / a)
		b = int(b % a)
print(c)


(n, v) = map(int, input().split())
sum = int(0)
while n != 0 and v != 0:
	if n <= v and n != 0:
		sum = sum + int(v / n)
		v = v % n
	elif v < n and v != 0:
		sum = sum + int(n / v)
		n = n % v
print(int(sum))


__author__ = 'artyom'
(a, b) = sorted(map(int, input().split()))
c = 1
while b > a:
	d = b - a
	r = d // a
	if d % a > 0:
		r += 1
	c += r
	(a, b) = (b - r * a, a)
print(c)


s = list(map(int, input().split()))
[a, b] = s
k = 0
while not (a == b or b == 0):
	if a >= 2 * b:
		k += a // b
		r = a % b
		a = b
		b = r
	else:
		k += 1
		c = a
		a = b
		b = c - b
if b == 0:
	print(k)
else:
	print(k + 1)


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


(a, b) = map(int, input().split())
k = 0
while a != 0 and b != 0:
	if a >= 2 * b:
		k += (a - a % b) / b
		a = a % b
	elif b >= 2 * a:
		k += (b - b % a) / a
		b = b % a
	elif a > b:
		k += 1
		a -= b
	elif b > a:
		k += 1
		b -= a
print(round(k))


s = str(input())
n = s.split()
a = int(n[0])
b = int(n[1])
c = 0
x = 0
while a % b != 0:
	c = a // b
	x = x + c
	d = b
	b = a % b
	a = d
x = x + a // b
print(x)


(a, b) = map(int, input().split())
a = max(a, b)
b = min(a, b)
ans = 0
while b > 1:
	ans += a // b
	(a, b) = (b, a % b)
	if not b:
		break
if b == 1:
	ans += a
print(ans)


__author__ = 'catman'
(a, b) = map(int, input().split())
count = 0
while True:
	if a > b:
		t = a // b
		a = a - t * b
	else:
		t = b // a
		b = b - t * a
	count += t
	if a == 0 or b == 0:
		break
	elif a == 1 or b == 1:
		if a == 1:
			count += b
		else:
			count += a
		break
print(count)


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


from sys import stdin
max_val = int(10000000000000.0)
min_val = int(-10000000000000.0)

def read_int():
	return int(stdin.readline())

def read_ints():
	return [int(x) for x in stdin.readline().split()]

def read_str():
	return input()

def read_strs():
	return [x for x in stdin.readline().split()]
(a, b) = sorted(read_ints())
cnt = 0
while b:
	cnt += a // b
	(a, b) = (b, a % b)
print(cnt)


(a, b) = [int(i) for i in input().split()]
cnt = 0
while True:
	if a == 0 or b == 0:
		break
	if a == b:
		cnt += 1
		break
	else:
		if a < b:
			c = b
			b = a
			a = c
		cnt += a // b
		c = a % b
		a = b
		b = c
print(cnt)


import sys
inf = float('inf')
from math import ceil, floor, log, log2, sqrt, factorial, pow, pi, gcd

def powerMod(x, y):
	res = 1
	while y > 0:
		if y & 1:
			res = res * x
		y = y >> 1
		x = x * x
	return res
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
(mod, MOD) = (1000000007, 998244353)
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

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()
maxi = max(a, b)
mini = min(a, b)
if maxi == mini:
	print(1)
	exit()
if maxi == 1 or mini == 1:
	print(max(maxi, mini))
	exit()
flag = 0
count = 0
while maxi != 1 and mini != 1 and (maxi != mini):
	count += maxi // mini
	a = mini
	b = maxi % mini
	maxi = max(a, b)
	mini = min(a, b)
	if mini == 1 and maxi > 1:
		flag = 1
		break
	if mini == 0:
		break
if flag == 1:
	count += max(maxi, mini)
print(count)


import unittest
import sys
import re
import random

class Paper:

	def __init__(self, args):
		self.args = args
		self.cur = self.args
		self.num = 0

	def iterate(self):
		if self.cur[0] < self.cur[1]:
			self.cur = (self.cur[1], self.cur[0])
		self.num += self.cur[0] // self.cur[1]
		remainder = self.cur[0] % self.cur[1]
		self.cur = (remainder, self.cur[1])
		return 1 if remainder else 0

	def calculate(self):
		while self.iterate():
			pass
		return self.num

def decode_inputs(inputs):
	ilist = [int(i) for i in inputs.split()]
	args = tuple(ilist)
	return args

def calculate(inputs):
	return Paper(decode_inputs(inputs)).calculate()

def main():
	inputs = input()
	print(calculate(inputs))

class unitTests(unittest.TestCase):

	def test_decode_inputs(self):
		self.assertEqual(decode_inputs('2 5'), (2, 5))

	def test_Paper_class__basic_functions(self):
		d = Paper((1, 2))
		self.assertEqual(d.args[0], 1)
		self.assertEqual(d.cur[0], 1)
		d = Paper((2, 2))
		self.assertEqual(d.iterate(), 0)
		self.assertEqual(d.num, 1)
		d = Paper((10, 3))
		self.assertEqual(d.iterate(), 1)
		self.assertEqual(d.cur, (1, 3))
		self.assertEqual(d.num, 3)

	def test_calculate(self):
		self.assertEqual(calculate('2 2'), 1)
		self.assertEqual(calculate('10 3'), 6)
		self.assertEqual(calculate('10 7'), 6)
		self.assertEqual(calculate('1000000000000 1'), 1000000000000)
if sys.argv[-1] == '-ut':
	unittest.main(argv=[' '])
main()


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


import sys, math
inp = input().split()
a = int(inp[0])
b = int(inp[1])
ans = 0
while a > 0 and b > 0:
	if a >= b:
		ans += a // b
		a = a % b
	else:
		ans += b // a
		b = b % a
print(ans)


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


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


l = list(map(int, input().split()))
c = 0
while min(l) > 0:
	a = l.index(max(l))
	c += l[a] // l[1 - a]
	l[a] = l[a] % l[1 - a]
print(c)


gi = lambda : list(map(int, input().strip().split()))
(a, b) = gi()
ans = 0
while a and b:
	(a, b) = (max(a, b), min(a, b))
	ans += a // b
	a -= a // b * b
print(ans)


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


my_str = input().split()
(a, b) = (int(my_str[0]), int(my_str[1]))
c = 0
while a > b and b > 0:
	t = a
	a = b
	c += int(t / b)
	b = t % b
	if b > a:
		t = a
		a = b
		b = t
print(c)


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


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


def paper(c, d):
	count = 0
	while d != 0:
		count += c // d
		(c, d) = (d, c % d)
	return count
(a, b) = [int(i) for i in input().split()]
print(paper(a, b))


def getInput():
	tableau = input().split()
	tableau[0] = int(tableau[0])
	tableau[1] = int(tableau[1])
	return (tableau[0], tableau[1])

def solve(a, b):
	compteur = 0
	while b > 0:
		compteur += a // b
		a -= a // b * b
		if a < b:
			(a, b) = (b, a)
	return compteur
(a, b) = getInput()
print(solve(a, b))


(n, m) = [int(i) for i in input().split()]

def swap(n, m):
	if n < m:
		nn = n
		n = m
		m = nn
	return (n, m)

def f(n, m):
	(n, m) = swap(n, m)
	if n % m == 0:
		return n // m
	if m == 1:
		return n
	return n // m + f(n - n // m * m, m)
print(f(n, m))


(a, b) = map(int, input().split())
ans = 0
while a != b:
	if a % b == 0:
		ans += a // b
		break
	temp = a
	fact = a // b
	a = max(abs(a - b * fact), b)
	b = temp - a * fact
	ans += 1 * fact
print(ans)


s = input()
a = s.split()
for i in range(len(a)):
	a[i] = int(a[i])
i = 0
while a[1] != a[0]:
	if a[1] > a[0]:
		i += int(a[1] / a[0])
		a[1] %= a[0]
	else:
		i += int(a[0] / a[1])
		a[0] %= a[1]
	if a[1] == 0 or a[0] == 0:
		break
print(i)


(a, b) = map(int, input().split())
x = 0
while a != b:
	if a - 100000000 * b > 0:
		a -= 100000000 * b
		if a < b:
			(b, a) = (a, b)
		x += 100000000
	elif a - 1000000 * b > 0:
		a -= 1000000 * b
		if a < b:
			(b, a) = (a, b)
		x += 1000000
	elif a - 10000 * b > 0:
		a -= 10000 * b
		if a < b:
			(b, a) = (a, b)
		x += 10000
	elif a - 100 * b > 0:
		a -= 100 * b
		if a < b:
			(b, a) = (a, b)
		x += 100
	elif a - b > 0:
		a -= b
		if a < b:
			(b, a) = (a, b)
		x += 1
print(x + 1)


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


import time
import collections

class Time_test:

	def __enter__(self):
		self.enter_time = time.time()

	def __exit__(self, exc_type, exc_val, exc_tb):
		print('Command was executed in', time.time() - self.enter_time)
(n, m) = [int(x) for x in input().split()]
counter = 0
while True:
	tmp = max(n, m) // min(n, m)
	if m > n:
		m -= n * tmp
	else:
		n -= m * tmp
	counter += tmp
	if n == 0 or m == 0:
		break
print(counter)


(x, y) = map(int, input().split())
ctr = 0
while x > 0:
	if y > x:
		(x, y) = (y, x)
	ctr += x // y
	x = x % y
print(ctr)


def main():
	(a, b) = [int(item) for item in input().strip().split(' ')]
	count = 0
	while a % b != 0:
		count += int(a / b)
		(a, b) = (b, a % b)
		if a < b:
			(a, b) = (b, a)
	count += a / b
	print(int(count))
main()


n = input().split()
a = int(n[0])
b = int(n[1])
count = 0
while not (a == b or a == 0 or b == 0):
	if a > b:
		x = int(a / b)
		a -= x * b
	else:
		x = int(b / a)
		b -= x * a
	count += x
print(count)


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