You've got two numbers. As long as they are both larger than zero, they go through the same operation: subtract the lesser number from the larger one. If they equal substract one number from the another. For example, one operation transforms pair (4,17) to pair (4,13), it transforms (5,5) to (0,5).

You've got some number of pairs (a_{i}, b_{i}). How many operations will be performed for each of them?


-----Input-----

The first line contains the number of pairs n (1  ≤  n  ≤  1000). Then follow n lines, each line contains a pair of positive integers a_{i}, b_{i} (1  ≤  a_{i},  b_{i}  ≤  10^9).


-----Output-----

Print the sought number of operations for each pair on a single line.


-----Examples-----
Input
2
4 17
7 987654321

Output
8
141093479

Difficulty: EASY
Tags: Number theory

Mathematics
Expected Time Complexity: O(1)

Starter code:

Solutions:
for i in range(int(input())):
	(a, b) = map(int, input().split())
	operations = 0
	(a, b) = (max(a, b), min(a, b))
	while b != 0:
		operations += a // b
		a -= a // b * b
		(a, b) = (max(a, b), min(a, b))
	print(operations)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = 0
	while min(a, b) != 0:
		ma = max(a, b)
		mi = min(a, b)
		a = mi
		b = ma
		c += b // a
		b = b % a
	print(c)


for i in range(int(input())):
	(a, b) = list(map(int, input().split()))
	c = 0
	while a > 0 and b > 0:
		A = max(a, b)
		B = min(a, b)
		if A % B == 0:
			c += A / B
			break
		else:
			c += int(A / B)
			a = A % B
			b = B
	print(int(c))


n = int(input())
for i in range(n):
	(x, y) = map(int, input().split())
	step = 0
	(a, b) = (max(x, y), min(x, y))
	while a % b != 0:
		step = step + a // b
		t = b
		b = a % t
		a = t
	print(step + a // b)


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


t = int(input())
ans = ''
for j in range(t):
	ab = input().split()
	a = int(ab[0])
	b = int(ab[1])
	k = 0
	while a > 0 and b > 0:
		if a >= b:
			k += a // b
			a %= b
		else:
			k += b // a
			b %= a
	ans += str(k) + '\n'
print(ans)


from math import ceil
for i in range(int(input())):
	(X, Count) = (list(map(int, input().split())), 0)
	while X[0] != X[1]:
		X = sorted(X)
		Count += ceil((X[1] - X[0]) / X[0])
		X[1] -= ceil((X[1] - X[0]) / X[0]) * X[0]
	print(Count + 1)


from collections import deque
from collections import OrderedDict
import math
import sys
import os
from io import BytesIO
import threading
import bisect
import heapq
input = lambda : sys.stdin.readline().rstrip('\r\n')
for i in range(int(input())):
	(a, b) = map(int, input().split())
	answer = 0
	if a < b:
		(a, b) = (b, a)
	while a != 0 and b != 0:
		answer += a // b
		a = a % b
		(a, b) = (b, a)
	print(answer)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	ans = 0
	while a * b != 0:
		if a > b:
			t = a // b
			a %= b
		else:
			t = b // a
			b %= a
		ans += t
	print(ans)


t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	ans = 0
	while a != 0 and b != 0:
		if a > b:
			(a, b) = (b, a)
		ans += b // a
		b %= a
	print(ans)


T = int(input())
for t in range(T):
	(x, y) = [int(n) for n in input().split()]
	ops = 0
	while x and y:
		if x < y:
			ops += int(y / x)
			y = y % x
		elif y < x:
			ops += int(x / y)
			x = x % y
		else:
			ops += 1
			break
	print(ops)


numCases = int(input())
for c in range(numCases):
	inp = input().split()
	a = int(inp[0])
	b = int(inp[1])
	count = 0
	flag = False
	while flag == False:
		if a == 0 or b == 0:
			print(count)
			break
		if a > b:
			times = a // b
			count += times
			a = a - b * times
		elif a < b:
			times = b // a
			count += times
			b = b - a * times
		else:
			print(count + 1)
			flag = True


t = int(input())

def ans(a, b):
	if a <= 0 or b <= 0:
		return 0
	(k, j) = (min(a, b), max(a, b))
	v = j // k
	j = j - v * k
	return v + ans(k, j)
for _ in range(t):
	(a, b) = [int(x) for x in input().split()]
	print(ans(a, b))


import sys
import math
import itertools
import collections

def getdict(n):
	d = {}
	if type(n) is list or type(n) is str:
		for i in n:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
	else:
		for i in range(n):
			t = ii()
			if t in d:
				d[t] += 1
			else:
				d[t] = 1
	return d

def divs(n, start=1):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def cdiv(n, k):
	return n // k + (n % k != 0)

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

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

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

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

def wr(arr):
	return '\n'.join(map(str, arr))

def revn(n):
	return int(str(n)[::-1])

def prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(math.sqrt(n)) + 1
	for d in range(3, sqr, 2):
		if n % d == 0:
			return False
	return True
n = ii()
for i in range(n):
	(a, b) = sorted(mi())
	ans = 0
	while a > 0:
		ans += b // a
		t = b % a
		b = a
		a = t
	print(ans)


n = int(input())
for i in range(n):
	(n1, n2) = map(int, input().split())
	count = 0
	while n1 != 0 and n2 != 0:
		if n1 >= n2:
			count = count + int(n1 / n2)
			n1 = n1 % n2
		else:
			count = count + int(n2 / n1)
			n2 = n2 % n1
	print(count)


from math import ceil
for _ in range(int(input())):
	m = 0
	(a, b) = list(map(int, input().split()))
	while a != 0 and b != 0:
		if a >= b:
			m += a // b
			a = a % b
		else:
			m += b // a
			b = b % a
	print(m)


for u in range(int(input())):
	(x, y) = map(int, input().split())
	c = 0
	while x > 0 and y > 0:
		if x >= y:
			c = c + x // y
			x %= y
		else:
			c = c + y // x
			y = y % x
	print(c)


for i in range(int(input())):
	l = list(map(int, input().split()))
	a = min(l)
	b = max(l)
	t = 0
	while a > 0 and b > 0:
		c = b // a
		t += c
		b -= a * c
		l = [a, b]
		a = min(l)
		b = max(l)
	print(t)


def solver(pc, py):
	if py % pc == 0:
		return py // pc
	return py // pc + solver(py % pc, pc)
for i in range(int(input())):
	(pc, pr) = map(int, input().split())
	print(solver(pc, pr))


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	cn = 0
	while a != 0 and b != 0:
		cn += b // a
		(a, b) = (b % a, a)
	print(cn)


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


import decimal
D = decimal.Decimal
n = int(input())
for _ in range(n):
	l1 = [int(x) for x in input().split()]
	ans = 0
	while l1[0] != 0 and l1[1] != 0:
		crit = min(l1)
		if crit == l1[0]:
			ans += int(D(l1[1] / l1[0]))
			l1[1] = l1[1] % l1[0]
		else:
			ans += int(D(l1[0] / l1[1]))
			l1[0] = l1[0] % l1[1]
	print(ans)


def substraction(a, b):
	if a == 0 or b == 0:
		return 0
	elif a > b:
		count = a // b
		return substraction(a % b, b) + count
	else:
		count = b // a
		return substraction(a, b % a) + count
t = int(input())
lst = []
res = []
for i in range(0, t):
	lst = [int(i) for i in input().split()]
	ele = substraction(lst[0], lst[1])
	res.append(ele)
for i in range(0, t):
	print(res[i])


for _ in range(int(input())):
	(a, b) = (int(s) for s in input().split())
	count = 0
	if a > b:
		(a, b) = (b, a)
	while a > 0 and b > 0:
		count += b // a
		b %= a
		(a, b) = (b, a)
	print(count)


k = int(input())
for i in range(k):
	(x, y) = map(int, input().split())
	if x > y:
		(x, y) = (x, y)
	ans = 0
	while x > 0:
		ans += y // x
		y %= x
		(x, y) = (y, x)
	print(ans)


def subs(a, b):
	if a > b:
		(a, b) = (b, a)
	if b % a == 0:
		return b // a
	else:
		return b // a + subs(b % a, a)
count = int(input())
for _ in range(count):
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	print(subs(a, b))


import sys
import math
n = int(sys.stdin.readline())
for i in range(n):
	(a, b) = [int(x) for x in sys.stdin.readline().split()]
	v = 0
	while a >= 1 and b >= 1:
		if a < b:
			v += int(b / a)
			b %= a
		else:
			v += int(a / b)
			a %= b
	print(v)


testcase = int(input())
for i in range(testcase):
	(a, b) = list(map(int, input().split()))
	count = 0
	while a > 0 and b > 0:
		if a >= b:
			vag = a // b
			count += vag
			rem = a % b
			a = rem
		else:
			vag = b // a
			count += vag
			rem = b % a
			b = rem
	print(count)


import sys
n = int(sys.stdin.readline())
for i in range(n):
	[a, b] = list(map(int, sys.stdin.readline().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)


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	con = 0
	while True:
		if b > a:
			(a, b) = (b, a)
		con += a // b
		if a % b != 0:
			a = a % b
		else:
			break
	print(con)


for _ in range(int(input())):
	(a, b) = map(int, 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
		else:
			c += 1
			break
	print(c)


for _ in range(int(input())):
	(n, m) = sorted(map(int, input().split()))
	count = 0
	while n > 0:
		count += m // n
		m = m % n
		(n, m) = sorted([n, m])
	print(count)


import sys
num_test_cases = int(sys.stdin.readline().rstrip())
for t in range(0, num_test_cases):
	temp = sys.stdin.readline().rstrip()
	line = temp.split(' ')
	num1 = int(line[0])
	num2 = int(line[1])
	count = 0
	while num1 > 0 and num2 > 0:
		if num1 <= num2:
			count += num2 // num1
			num2 %= num1
		else:
			count += num1 // num2
			num1 %= num2
	print(count, end=' ')
print()


def f(a, b):
	global ans
	maks = max(a, b)
	mins = min(a, b)
	ans += maks // mins
	if mins == 1:
		return ans
	elif maks % mins == 0:
		return ans
	else:
		return f(maks % mins, mins)
for i in range(int(input())):
	(a, b) = list(map(int, input().split()))
	ans = 0
	print(f(a, b))


import math

def countSteps(x, y):
	if x % y == 0:
		return math.floor(x / y)
	return math.floor(x / y + countSteps(y, x % y))
input_1 = eval(input())
for i in range(input_1):
	(x, y) = input().split()
	x = int(x)
	y = int(y)
	print(countSteps(x, y))


num_pairs = int(input())
arr = []
for pair in range(num_pairs):
	operations = 0
	val = input().split(' ')
	lesser_num = int(val[0]) if int(val[0]) < int(val[1]) else int(val[1])
	greater_num = int(val[1]) if int(val[0]) <= int(val[1]) else int(val[0])
	while greater_num > 0 and lesser_num > 0:
		difference = greater_num - lesser_num
		difference = difference // lesser_num + 1
		operations += difference
		greater_num = greater_num - difference * lesser_num
		temp = lesser_num
		lesser_num = greater_num
		greater_num = temp
	arr.append(operations)
for val in range(len(arr)):
	print(str(arr[val]))


def solve():
	(a, b) = map(int, input().rstrip().split())
	count = 0
	if b > a:
		(a, b) = (b, a)
	while not (a == 0 or b == 0):
		count += a // b
		a %= b
		(a, b) = (b, a)
	print(count)
t = int(input())
for _ in range(t):
	solve()


for i in range(int(input())):
	(a, b) = map(int, input().split())
	if a > b:
		(a, b) = (b, a)
	s = 0
	if a > 0:
		s = b // a
		(a, b) = (b - s * a, a)
		while a > 0:
			k = b // a
			(a, b) = (b - k * a, a)
			s += k
	print(s)


n = int(input())
for i in range(n):
	(x, y) = map(int, input().split())
	ans = 0
	while x > 0 and y > 0:
		if x > y:
			(x, y) = (y, x)
		ans = ans + y // x
		y = y % x
	print(ans)


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


def num_subtractions(x, y):
	num = 0
	while x and y:
		if x >= y:
			num += x // y
			x %= y
		else:
			num += y // x
			y %= x
	return num
for _ in range(int(input())):
	(x, y) = list(map(lambda x: int(x), input().split()))
	print(num_subtractions(x, y))


n = int(input())
array = []
for _ in range(n):
	array.append(list(map(int, input().split())))
for i in range(len(array)):
	count = 0
	if array[i][0] == array[i][1]:
		count += 1
	else:
		maximum = 0
		minimum = 0
		if array[i][0] > array[i][1]:
			maximum = array[i][0]
			minimum = array[i][1]
		elif array[i][0] < array[i][1]:
			maximum = array[i][1]
			minimum = array[i][0]
		while True:
			count += maximum // minimum
			temp = maximum - maximum // minimum * minimum
			maximum = minimum
			minimum = temp
			if maximum == minimum:
				count += 1
				break
			if minimum == 0 or maximum == 0:
				break
	print(count)


testCases = int(input().strip())
for _ in range(testCases):
	total = 0
	nums = input().split(' ')
	smaller = int(nums[0])
	bigger = int(nums[1])
	while smaller > 0 and bigger > 0:
		total += bigger // smaller
		bigger = bigger % smaller
		(bigger, smaller) = (smaller, bigger)
	print(total)


from sys import stdin

def read_lines(sep=' ', input_type=None):
	_lines = stdin.readlines()
	cast = input_type is not None
	lines = []
	for line in _lines:
		line = line[:-1].split(sep)
		if cast:
			line = [input_type(x) for x in line]
		lines.append(line)
	return lines
import collections

def numz(a, b):
	if a and b:
		if b > a:
			(a, b) = (b, a)
		(d, m) = divmod(a, b)
		return d + numz(b, m)
	else:
		return 0
lines = read_lines(input_type=int)
lines = lines[1:]
for line in lines:
	print(numz(*line))


t = int(input())
while t > 0:
	res = 0
	(a, b) = map(int, input().split())
	l = min(a, b)
	m = max(a, b)
	while l > 0:
		res += m // l
		m = m % l
		temp = l
		l = m
		m = temp
	print(res)
	t -= 1


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	c = 0
	while a > 0 and b > 0:
		if b > a:
			(a, b) = (b, a)
		d = a // b
		a = a - d * b
		c += d
	print(c)


def solution(a, b):
	res = 0
	if b > a:
		(a, b) = (b, a)
	while a > 0 and b > 0:
		tmp = a // b
		a -= tmp * b
		res += tmp
		if b > a:
			(a, b) = (b, a)
	return res
n = input()
res = []
for _ in range(int(n)):
	(a, b) = input().split()
	res.append([int(a), int(b)])
for (a, b) in res:
	print(solution(a, b))


def minus(a, b):
	count = 0
	while a > 0 and b > 0:
		if a > b:
			(a, b) = (b, a)
		count += b // a
		b %= a
	return count
n = int(input())
a = list()
for i in range(n):
	(A, B) = [int(i) for i in input().split()]
	a.append([A, B])
c = list()
for elem in a:
	c.append(minus(elem[0], elem[1]))
print(*c, sep='\n')


cases = int(input())
for i in range(cases):
	(a, b) = map(int, input().split())
	total = 0
	while a > 0 and b > 0:
		total += max(a, b) // min(a, b)
		if a >= b:
			a %= b
		else:
			b %= a
	print(total)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	r = max(a, b)
	k = min(a, b)
	c = 0
	while True:
		c += r // k
		l = r % k
		a = l
		b = k
		r = max(a, b)
		k = min(a, b)
		if l == 0:
			break
	print(c)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	t = 0
	while x > 0 and y > 0:
		if x > y:
			t += x // y
			x = x % y
		else:
			t += y // x
			y = y % x
	print(t)


n = int(input())
for i in range(n):
	(x, y) = map(int, input().split())
	if x > y:
		(x, y) = (y, x)
	a = 0
	while x > 0:
		a += y // x
		y %= x
		(x, y) = (y, x)
	print(a)


numTests = int(input())
results = []
for test in range(0, numTests):
	inputs = list(map(int, input().split()))
	num1 = inputs[0]
	num2 = inputs[1]
	count = 0
	while num1 != 0 and num2 != 0:
		if num1 < num2:
			count += num2 // num1
			num2 = num2 % num1
		elif num1 > num2:
			count += num1 // num2
			num1 = num1 % num2
		else:
			count += 1
			break
	results.append(count)
for result in results:
	print(result)


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


n = int(input())
for i in range(n):
	a = list(map(int, input().split()))
	c = 0
	while a[0] and a[1]:
		if a[0] < a[1]:
			c = c + a[1] // a[0]
			a[1] = a[1] % a[0]
		else:
			c = c + a[0] // a[1]
			a[0] = a[0] % a[1]
	print(c)


def GCDFunc(a, b):
	if a == 0:
		return 0
	else:
		Z = GCDFunc(b % a, a) + b // a
		return Z
for i in range(int(input())):
	(a, b) = map(int, input().split())
	print(GCDFunc(a, b))


cases = int(input())
while cases:
	cases -= 1
	(a, b) = map(int, input().split())
	ans = 0
	while a > 0 and b > 0:
		if a < b:
			(a, b) = (b, a)
		ans += a // b
		a = a % b
	print(ans)


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

def sub(a, b):
	if a == 0:
		return 0
	else:
		return b // a + sub(b % a, a)
n = I()
for i in range(n):
	(a, b) = M()
	if a <= b:
		print(sub(a, b))
	else:
		print(sub(b, a))


import sys
import math
input = sys.stdin.readline

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

def inps():
	return str(input())

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

def inlst():
	return list(map(str, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

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

def operations(s, l):
	counts = 0
	while s != 0:
		counts += math.floor(l / s)
		temp = s
		s = l % s
		l = temp
	return counts
n = inp()
q = []
for i in range(n):
	q.append(inlt())
for i in q:
	print(operations(i[0], i[1]))


def subtraction(x, y):
	if x and y:
		ret = y // x
		mod = y % x
		return ret + subtraction(mod, x)
	else:
		return 0
tests = int(input())
for x in range(tests):
	line = list(map(int, input().split()))
	f = line[0]
	s = line[1]
	print(subtraction(s, f))


n = int(input())
ab = []
for _ in range(n):
	ab.append(list(map(int, input().split())))
for item in ab:
	(a, b) = (item[0], item[1])
	cnt = 0
	while a != 0 and b != 0:
		if a <= b:
			m = b // a
			cnt += m
			b -= a * m
		elif a > b:
			m = a // b
			cnt += m
			a -= b * m
	print(cnt)


a = int(input())
for i in range(a):
	b = input().split()
	c = int(b[0])
	d = int(b[1])
	count = 0
	if c < d:
		(c, d) = (d, c)
	while c != 0 and d != 0:
		count += c // d
		e = d
		d = c % d
		c = e
	print(count)


def reduce(a, b):
	if a <= 0 or b <= 0:
		return 0
	if a == b:
		return 1
	if a < b:
		(a, b) = (b, a)
	q = a // b
	r = a % b
	return q + reduce(b, r)
num_tests = int(input())
for _ in range(num_tests):
	(a, b) = map(int, input().split())
	print(reduce(a, b))


for i in range(int(input())):
	(a, b) = list(map(int, input().split()))
	(a, b) = (max(a, b), min(a, b))
	knt = 0
	while a != 0 and b != 0:
		knt += a // b
		(a, b) = (b, a % b)
	print(knt)


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	count = 0
	while a > 0 and b > 0:
		k = max(a, b) // min(a, b)
		count += k
		if a >= b:
			a -= k * b
		else:
			b -= k * a
	print(count)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = 0
	while a and b:
		if a >= b:
			c += a // b
			a %= b
		if a < b and a != 0:
			c += b // a
			b %= a
	print(c)


import sys
import math
get_string = lambda : sys.stdin.readline().strip()
get_int_list = lambda : list(map(int, sys.stdin.readline().strip().split()))
get_int = lambda : int(sys.stdin.readline())
for i in range(get_int()):
	(a, b) = get_int_list()
	cnt = 0
	while a != 0 and b != 0:
		(a, b) = (min(a, b), max(a, b))
		d = b // a
		cnt += d
		b -= d * a
	print(cnt)


def process(a, b):
	mini = min(a, b)
	maxi = max(a, b)
	cnt = 0
	while maxi != mini and maxi >= 0 and (mini > 0):
		cnt += maxi // mini
		maxi = maxi % mini
		if mini > maxi:
			(maxi, mini) = (mini, maxi)
	if mini == maxi and mini != 0:
		cnt += 1
	return cnt
t = int(input())
while t > 0:
	(a, b) = map(int, input().split())
	print(process(a, b))
	t -= 1


n = input()
n1 = int(n)
c = []
for i in range(0, n1):
	z4 = 0
	(p, q) = input().split()
	a = int(p)
	b = int(q)
	while a != 0 and b != 0:
		z1 = z3 = 0
		if a <= b:
			z = b / a
			z1 = int(z)
			b = b - z1 * a
		if b <= a and b != 0:
			z2 = a / b
			z3 = int(z2)
			a = a - z3 * b
		z4 = z4 + z1 + z3
	c.append(z4)
l = len(c)
for j in range(0, l):
	print(c[j])


n = int(input())
for i in range(n):
	t = input()
	t = list(t.split())
	a = int(t[0])
	b = int(t[1])
	if a > b:
		(a, b) = (b, a)
	count = 0
	while a != 0 and b != 0:
		count += b // a
		b %= a
		if a > b:
			(a, b) = (b, a)
	print(count)


N = int(input())
for _ in range(N):
	(a, b) = map(int, input().split())
	if a < b:
		(a, b) = (b, a)
	cnt = 0
	while b != 0:
		cnt += a // b
		(a, b) = (b, a % b)
	print(cnt)


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	steps = 0
	while a > 0 and b > 0:
		if a >= b:
			steps += a // b
			a = a % b
		else:
			steps += b // a
			b = b % a
	print(steps)


for i in range(int(input())):
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	ma = max(a, b)
	mi = min(a, b)
	count = 0
	while True:
		if ma % mi == 0:
			count = count + ma // mi
			break
		else:
			count = count + ma // mi
			d = ma % mi
			ma = mi
			mi = d
	print(count)


nn = int(input())
for ffkfkd in range(nn):
	inp = input().split()
	a = int(inp[0])
	b = int(inp[1])
	n = 0
	while a != 0 and b != 0:
		if a > b:
			n += a // b
			a = a % b
		else:
			n += b // a
			b = b % a
	print(n)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	count = 0
	if x == y:
		print(1)
	else:
		while y > 0 and x > 0:
			if y == max(x, y):
				count += y // x
				y = y % x
			else:
				count += x // y
				x = x % y
		print(count)


def count_ops(a, b):
	if a and b:
		if a < b:
			(a, b) = (b, a)
		return a // b + count_ops(b, a % b)
	return 0
for _ in range(int(input())):
	print(count_ops(*map(int, input().split())))


for s in [*open(0)][1:]:
	(a, b) = map(int, s.split())
	r = 0
	while a and b:
		if b > a:
			r += 0 - -(b - a) // a
			b %= a
		else:
			r += 0 - -(a - b) // b
			a %= b
	print(r + 1)


def subtract(a, b):
	m = max(a, b)
	n = min(a, b)
	if m % n == 0:
		result = int(m / n)
		print(result)
	else:
		sum = 0
		while m % n != 0:
			r = m % n
			sum += int(m / n)
			m = n
			n = r
		sum += int(m / n)
		print(sum)
case = int(input())
while case > 0:
	(a, b) = map(int, input().split())
	subtract(a, b)
	case -= 1


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


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


__author__ = 'markdaniel'

def main():
	(num1, num2) = [int(x) for x in input().split(' ')]
	maxval = max(num1, num2)
	minval = min(num1, num2)
	ops = 0
	while maxval > 0 and minval > 0:
		remainderMultiple = (maxval - minval) // minval
		maxval -= remainderMultiple * minval
		ops += remainderMultiple
		maxval -= minval
		ops += 1
		if maxval < minval:
			temp = maxval
			maxval = minval
			minval = temp
	return ops
cases = int(input())
for i in range(cases):
	print(main())


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


from sys import stdin
T = int(stdin.readline().rstrip())
for t in range(T):
	(a, b) = map(int, stdin.readline().rstrip().split())
	count = 0
	if a < b:
		temp = a
		a = b
		b = temp
	while b != 0:
		count += a // b
		a = a % b
		temp = a
		a = b
		b = temp
	print(count)


import sys
pairs = int(sys.stdin.readline())
for x in range(pairs):
	(a, b) = map(int, sys.stdin.readline().split(' '))
	r = 0
	times = 0
	rem = 0
	while True:
		times = max(a, b) // min(a, b)
		r += times
		rem = max(a, b) % min(a, b)
		if rem == 0:
			break
		a = min(a, b)
		b = rem
	print(r)


def f(l):
	(b, s) = (max(l), min(l))
	c = 0
	while s > 0:
		c += b // s
		t = s
		s = b % s
		b = t
	return c
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	print(f(l))


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a > b:
		(lar, small) = (a, b)
	else:
		(lar, small) = (b, a)
	t = 0
	while lar > 0 and small > 0:
		if lar % small == 0:
			t += lar // small
			break
		else:
			t += lar // small
			lar = lar % small + small
			k = small
			small = lar - k
			lar = k
	print(t)


def calculate(test):
	count = 0
	(a, b) = (max(test), min(test))
	while a != 0 and b != 0:
		count += a // b
		(a, b) = (b, a % b)
	print(count)
for i in range(int(input())):
	iSet = list(map(int, input().split()))
	calculate(iSet)


n = int(input())
for i in range(n):
	inp = input().split()
	a = int(inp[0])
	b = int(inp[1])
	count = 0
	while 1:
		if a == 0 or b == 0:
			break
		if a > b:
			count += a // b
			a = a % b
		else:
			count += b // a
			b = b % a
	print(count)


import sys

def get(a, b):
	if a == 0 or b == 0:
		return 0
	if a == b:
		return 1
	if a > b:
		return get(b, a)
	res = b // a
	b = b % a
	return get(b, a) + res
ntest = int(input())
for i in range(0, ntest):
	tmp = list(map(int, input().split()))
	a = tmp[0]
	b = tmp[1]
	print(get(a, b))


tt = int(input())
for i in range(tt):
	(a, b) = map(int, input().split())
	count = 0
	while a > 0 and b > 0:
		if a >= b:
			count += a // b
			a = a - a // b * b
		else:
			count += b // a
			b = b - b // a * a
	print(count)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	count = 0
	while min(a, b) != 0:
		x = max(a, b)
		y = min(a, b)
		a = y
		b = x
		count += b // a
		b = b % a
	print(count)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	sm = 0
	while a and b:
		sm += a // b
		t = b
		b = a % b
		a = t
	print(sm)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	cnt = 0
	while a != 0 and b != 0:
		(a, b) = (max(a, b), min(a, b))
		cnt += a // b
		a %= b
	print(cnt)


T = int(input())
answer = []
for t in range(T):
	(A, B) = input().split()
	A = int(A)
	B = int(B)
	x = 0
	if A > B:
		r = B
		B = A
		A = r
	while A > 0 and B > 0:
		r = B // A
		x += r
		r *= A
		B = B - r
		if A > B:
			r = B
			B = A
			A = r
	answer.append(x)
for t in range(T):
	print(answer[t])


import sys

def num_ops(low, high):
	if high % low == 0:
		return high // low
	else:
		return high // low + num_ops(high % low, low)

def main():
	n = int(sys.stdin.readline().strip())
	for _ in range(n):
		(low, high) = [int(i) for i in sys.stdin.readline().strip().split()]
		print(num_ops(low, high))
main()


n = int(input())
for i in range(0, n):
	ab = input().split()
	a = int(ab[0])
	b = int(ab[1])
	count = 0
	while a > 0 and b > 0:
		count += max(a, b) // min(a, b)
		temp = a
		a = max(temp, b) % min(temp, b)
		b = min(b, temp)
	print(count)


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	(a, b, c) = (0, 0, 0)
	while m != n:
		if max(m, n) % min(m, n) == 0:
			c = c + max(m, n) // min(m, n) - 1
			break
		else:
			c = c + max(m, n) // min(m, n)
			(m, n) = (min(m, n), max(m, n) % min(m, n))
	print(c + 1)


import math
n = int(input())
for i in range(n):
	l = list(map(int, input().split()))
	l.sort()
	c = 0
	while l[0] != l[1]:
		k = math.ceil((l[1] - l[0]) / l[0])
		l[1] = l[1] - k * l[0]
		c += k
		l.sort()
	print(c + 1)


n = int(input())
for i in range(n):
	st = input().split()
	st.sort()
	(a, b) = map(int, st)
	cnt = 0
	while a != 0:
		q = b // a
		cnt += q
		(a, b) = (b - q * a, a)
	print(cnt)


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


t = int(input())
for j in range(t):
	(a, b) = map(int, input().split(' '))
	(maxi, mini) = (max(a, b), min(a, b))
	sum1 = 0
	while mini:
		sum1 += maxi // mini
		(maxi, mini) = (mini, maxi % mini)
	print(sum1)


n = int(input())
for i in range(0, n):
	a = list(map(int, input().split()))
	l = 0
	d = 0
	while 1:
		l = l + a[1] // a[0]
		a[1] = a[1] % a[0]
		d = a[0]
		a[0] = a[1]
		a[1] = d
		if a[0] == 0:
			break
	print(l)


def convert(arr):
	arr = arr.split(' ')
	for i in range(len(arr)):
		arr[i] = int(arr[i])
	return arr
t = int(input())
ans = []
for i in range(t):
	s = input()
	num = convert(s)
	counter = 1
	while num[0] != num[1]:
		if num[0] > num[1]:
			tc = int((num[0] - num[1]) / num[1])
			if (num[0] - num[1]) % num[1] != 0:
				tc += 1
			counter += tc
			num[0] = num[0] - tc * num[1]
		else:
			tc = int((num[1] - num[0]) / num[0])
			if (num[1] - num[0]) % num[0] != 0:
				tc += 1
			counter += tc
			num[1] = num[1] - tc * num[0]
	ans.insert(i, counter)
for i in range(len(ans)):
	print(ans[i])


for i in range(int(input())):
	(a, b) = map(int, input().split(' '))
	c = 0
	remain = 10
	while remain != 0:
		maxi = max(a, b)
		c += max(a, b) // min(a, b)
		remain = max(a, b) % min(a, b)
		if maxi == a:
			a = remain
		else:
			b = remain
	print(c)


from math import ceil
for i in range(int(input())):
	(a, b) = map(int, input().split())
	c = 0
	while a > 0 and b > 0:
		if a < b:
			(a, b) = (b, a)
		d = a - b
		if d != 0:
			c += ceil(d / b)
			a -= b * ceil(d / b)
		else:
			c += 1
			(a, b) = (0, 0)
	print(c)


import sys
line = input().split(' ')
test_cases = int(line[0])
for tc in range(test_cases):
	line = input().split(' ')
	num1 = int(line[0])
	num2 = int(line[1])
	count = 0
	while num1 != 0 and num2 != 0:
		if num1 > num2:
			count += int(num1 / num2)
			num1 %= num2
		else:
			count += int(num2 / num1)
			num2 %= num1
	sys.stdout.write(str(count))
	if tc < test_cases - 1:
		sys.stdout.write('\n')


import sys
sys.setrecursionlimit(200000)
LI = lambda : list(map(int, sys.stdin.readline().split()))
MI = lambda : map(int, sys.stdin.readline().split())
SI = lambda : sys.stdin.readline().strip('\n')
II = lambda : int(sys.stdin.readline())
for _ in range(II()):
	(a, b) = sorted(MI())
	ans = 0
	while a and b:
		ans += b // a
		(a, b) = (b % a, a)
	print(ans)


def solve(a, b):
	m = max(a, b)
	n = min(a, b)
	if n == 0:
		return 0
	if m == n:
		return 1
	elif m % n == 0:
		return m // n
	k = m // n
	return k + solve(n, m - n * k)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(solve(a, b))


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


def solve(a, b):
	holder = [a, b]
	times = 0
	while holder[0] > 0 and holder[1] > 0:
		smaller = 0 if holder[0] < holder[1] else 1
		other = 1 - smaller
		times += holder[other] // holder[smaller]
		holder[other] = holder[other] % holder[smaller]
	return times

def main():
	cases = int(input())
	for _ in range(cases):
		(a, b) = map(int, input().split())
		print(solve(a, b))
main()


n = int(input())
y = []
for x in range(n):
	y.append(input())
for x in y:
	noop = 0
	lst1 = x.split()
	lst1 = [int(p) for p in lst1]
	ma = max(lst1)
	mi = min(lst1)
	while ma != 0 and mi != 0:
		b = ma // mi
		ma = ma - b * mi
		temp = ma
		ma = mi
		mi = temp
		noop += b
	print(noop)


n = int(input())
for i in range(n):
	ans = 0
	(a, b) = map(int, input().split())
	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)


t = int(input())

def e(a, b):
	return max(a, b) // min(a, b)
for i in range(t):
	(a, b) = map(int, input().split(' '))
	s = 0
	while b != 0 and a != 0:
		c = e(a, b)
		s += c
		if a > b:
			a -= c * b
		else:
			b -= c * a
	print(s)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	cnt = 0
	while min(x, y) != 0:
		(x, y) = (max(x, y), min(x, y))
		cnt += x // y
		x %= y
	print(cnt)


import math
n = int(input())
for _ in range(n):
	(a, b) = map(int, input().split())
	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)


import math
import sys

def solve(r, w):
	num_pairs = int(r.readline())
	pairs = []
	for _ in range(num_pairs):
		line_data = [int(v) for v in r.readline().split()]
		pairs.append((line_data[0], line_data[1]))
		num_1 = line_data[0]
		num_2 = line_data[1]
		ops = 0
		while num_1 > 0 and num_2 > 0:
			if num_1 > num_2:
				(num_1, num_2) = (num_2, num_1)
			ops += num_2 // num_1
			num_2 %= num_1
		print(ops)

def __starting_point():
	solve(sys.stdin, sys.stdout)
__starting_point()


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	res = 0
	while 1:
		if a > b and b != 0:
			res = res + a // b
			a = a % b
		elif a < b and a != 0:
			res = res + b // a
			b = b % a
		elif a == b and a != 0:
			res += 1
			break
		else:
			break
	print(res)


def get_problems():
	from sys import stdin
	getint = lambda : int(stdin.readline().strip())
	getints = lambda : [int(n) for n in stdin.readline().strip().split()]
	t = getint()
	for _ in range(t):
		yield tuple(getints())

def solve(a, b):
	(a, b) = sorted((a, b))
	ans = 0
	while a != 0:
		ans += b // a
		t = a
		a = b % a
		b = t
	return ans
problems = get_problems()
print('\n'.join(map(str, map(lambda problem: solve(*problem), problems))))


n = int(input())
for i in range(n):
	a = [int(x) for x in input().split(' ')]
	a.sort()
	ops = 0
	while a[0] > 0:
		ops += a[1] // a[0]
		a = [a[1] % a[0], a[0]]
	print(ops)


import math, sys

def solve(a, b):
	if a == b:
		return 1
	elif a == 0 or b == 0:
		return 0
	else:
		return math.floor(max(a, b) / min(a, b)) + solve(min(a, b), max(a, b) % min(a, b))

def main():
	n = int(input())
	for s in sys.stdin:
		(a, b) = [int(x) for x in s.split()]
		print(solve(a, b))
main()


import sys
numCases = int(sys.stdin.readline())
for i in range(numCases):
	(a, b) = sys.stdin.readline().split()
	a = int(a)
	b = int(b)
	total = 0
	largerNum = max(a, b)
	smallerNum = min(a, b)
	while True:
		div = int(largerNum / smallerNum)
		total += div
		rem = int(largerNum % (smallerNum * div))
		if rem == 0:
			break
		else:
			largerNum = smallerNum
			smallerNum = rem
	print(total)


n = int(input())
for _ in range(n):
	(a, b) = sorted(map(int, input().split()))
	r = 0
	while 1:
		(c, d) = (b // a, b % a)
		r += c
		(a, b) = (d, a)
		if d == 0:
			print(r)
			break


def func(a, b, tcount):
	while a > 0 and b > 0:
		if a <= b:
			tcount += b // a
			b = b % a
		else:
			tcount += a // b
			a = a % b
	return tcount
n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	tcount = 0
	k = func(a, b, tcount)
	print(k)


t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	(x, y) = (max(a, b), min(a, b))
	ans = 0
	run = True
	while run:
		ans += x // y
		mod = x % y
		if mod == 0:
			run = False
		x = max(mod, y)
		y = min(mod, y)
	print(ans)


def ops(a, b):
	(a, b) = (max(a, b), min(a, b))
	if a == b:
		return 1
	if a % b == 0:
		return a // b
	return a // b + ops(a - a // b * b, b)
t = int(input())
for q in range(t):
	(a, b) = [int(x) for x in input().split()]
	print(ops(a, b))


n = int(input())
for i in range(n):
	s = 0
	(a, b) = map(int, input().split())
	min1 = min(a, b)
	max1 = max(a, b)
	while min1 > 0 and max1 > 0:
		min2 = min1
		min1 = min(min1, max1)
		max1 = max(min2, max1)
		s += max1 // min1
		max1 -= max1 // min1 * min1
	print(s)


def operations(a, b):
	less = min(a, b)
	more = max(a, b)
	ops = 0
	while less > 0 and more > 0:
		ops += more // less
		more -= less * (more // less)
		(less, more) = (more, less)
	return ops
n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	print(operations(a, b))


import math

def countSteps(x, y):
	if x % y == 0:
		return math.floor(x / y)
	return math.floor(x / y + countSteps(y, x % y))
n = int(input())
c = []
for i in range(0, n):
	(x, y) = map(int, input().rstrip().split())
	count = countSteps(x, y)
	c.append(count)
for i in range(0, len(c)):
	print(c[i])


tc = int(input())
for i in range(tc):
	(m, n) = map(int, input().split())
	if m > n:
		(m, n) = (n, m)
	c = 0
	while m > 0:
		c += n // m
		n %= m
		(m, n) = (n, m)
	print(c)


def operate(a, b):
	if a > b:
		if (a - b) % b:
			return (a - b) // b
		else:
			return (a - b) // b + 1
	if b > a:
		if (b - a) % a:
			return (b - a) // a
		else:
			return (b - a) // a + 1
for x in range(int(input())):
	(a, b) = [int(x) for x in input().split()]
	count = 0
	while a != 0 and b != 0:
		if a > b:
			factor = (a - b) // b + 1
			a -= factor * b
			count += factor
		else:
			factor = (b - a) // a + 1
			b -= factor * a
			count += factor
	print(count)


from math import floor
pairs = int(input())
for i in range(pairs):
	nums = [int(x) for x in input().split(' ')]
	a = nums[0]
	b = nums[1]
	ops = 0
	while a > 0 and b > 0:
		if a < b:
			ops += floor(b / a)
			b = b % a
		else:
			ops += floor(a / b)
			a = a % b
	print(floor(ops))


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	c = 0
	while min(a, b) > 0:
		if a > b:
			c += a // b
			a = a % b
		elif b > a:
			c += b // a
			b = b % a
		else:
			b -= a
			c += 1
	print(c)


n = int(input())
for _ in range(n):
	(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 algo(a, b):
	if a > b:
		temp = a
		a = b
		b = temp
	if a == 0:
		return 0
	else:
		return b // a + algo(a, b % a)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(algo(a, b))


n = int(input())
pairs = [] * n
for _ in range(n):
	pairs.append(list(map(int, input().split())))
for pair in pairs:
	no_of_steps = 0
	while pair[0] > 0 and pair[1] > 0:
		if pair[0] >= pair[1]:
			no_of_steps += pair[0] // pair[1]
			pair[0] = pair[0] % pair[1]
		else:
			no_of_steps += pair[1] // pair[0]
			pair[1] = pair[1] % pair[0]
	print(no_of_steps)


n = int(input())
a = []
b = []
for _ in range(n):
	arr = list(map(int, input().split()))
	a.append(arr[0])
	b.append(arr[1])
for i in range(n):
	count = 0
	num1 = a[i]
	num2 = b[i]
	while num1 != 0 and num2 != 0:
		if num1 > num2:
			count += num1 // num2
			num1 = num1 % num2
		else:
			count += num2 // num1
			num2 = num2 % num1
	print(count)


from sys import stdin
input = stdin.buffer.readline
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	cnt = 0
	while min(a, b) > 0:
		if a < b:
			(a, b) = (b, a)
		cnt += a // b
		a %= b
	print(cnt)


def sol(a, b):
	if a > b:
		(a, b) = (b, a)
	ans = 0
	while a:
		ans += b // a
		(a, b) = (b % a, a)
	return ans
n = int(input())
for _ in range(n):
	(a, b) = map(int, input().split())
	print(sol(a, b))


f = lambda x, y: f(y % x, x) + y // x if x else 0
I = input
for _ in '0' * int(I()):
	(a, b) = map(int, I().split())
	print(f(a, b))


def calculate(a, b):
	operations = 0
	while a != 0 and b != 0:
		if a == b:
			b -= a
			operations += 1
		else:
			times = None
			if a > b:
				difference = a - b
				times = int(difference / b)
				if difference % b != 0 and b * (times + 1) <= a:
					times += 1
				a -= b * times
			else:
				difference = b - a
				times = int(difference / a)
				if difference % a != 0 and a * (times + 1) <= b:
					times += 1
				b -= a * times
			operations += times
	return operations

def main():
	num_tests = int(input())
	for test in range(num_tests):
		(a, b) = input().strip().split(' ')
		(a, b) = (int(a), int(b))
		print(str(calculate(a, b)))
main()


n = int(input())
i = 0
while i < n:
	a = list(map(int, input().split()))
	x = 0
	while a[0] > 0 and a[1] > 0:
		b = a[1] % a[0]
		x += a[1] // a[0]
		c = a[0]
		a.clear()
		a.append(c)
		a.append(b)
		a.sort()
	print(x)
	a = []
	i += 1


def larger(a, b, count):
	if b == 0:
		return count
	if a > b:
		(a, b) = (b, a)
	count += b // a
	count = larger(a, b % a, count)
	return count
testCase = input()
for _ in range(int(testCase)):
	a = list(map(int, input().split(' ')))
	print(larger(a[0], a[1], 0))


N = int(input())

def ans(a, b):
	if a == 0 or b == 0:
		return 0
	return a // b + ans(b, a % b)
for _ in range(N):
	(a, b) = input().split(' ')
	a = int(a)
	b = int(b)
	print(ans(a, b))


def solve(a, b):
	ans = 0
	(a, b) = (max(a, b), min(a, b))
	if b == 0:
		return ans
	else:
		ans += a // b
		return ans + solve(a % b, b)
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	print(solve(a, b))


from sys import stdin
N = int(stdin.readline())
for n in range(N):
	(a, b) = map(int, stdin.readline().split())
	(a, b) = (min(a, b), max(a, b))
	ops = 0
	while a > 0:
		ops += b // a
		(a, b) = (b % a, a)
	print(ops)


n = input()
ans = 0
for i in range(int(n)):
	ai_bi = input()
	ab = ai_bi.split()
	ab = list(map(int, ab))
	(a, b) = ab
	c = max(a, b)
	d = min(a, b)
	ans = c // d
	while c % d:
		temp = d
		d = c % d
		c = temp
		ans += c // d
	print(ans)
	ans = 0