You are standing at point $(0,0)$ on an infinite plane. In one step, you can move from some point $(x_f,y_f)$ to any point $(x_t,y_t)$ as long as the Euclidean distance, $\sqrt{(x_f-x_t)^2+(y_f-y_t)^2}$, between the two points is either $\boldsymbol{a}$ or $\boldsymbol{b}$. In other words, each step you take must be exactly $\boldsymbol{a}$ or $\boldsymbol{b}$ in length.

You are given $\textit{q}$ queries in the form of $\boldsymbol{a}$, $\boldsymbol{b}$, and $\boldsymbol{d}$. For each query, print the minimum number of steps it takes to get from point $(0,0)$ to point $\left(d,0\right)$ on a new line.

Input Format

The first line contains an integer, $\textit{q}$, denoting the number of queries you must process. 

Each of the $\textit{q}$ subsequent lines contains three space-separated integers describing the respective values of $\boldsymbol{a}$, $\boldsymbol{b}$, and $\boldsymbol{d}$ for a query. 

Constraints

$1\leq q\leq10^5$
$1\leq a<b\leq10^9$
$0\leq d\leq10^9$

Output Format

For each query, print the minimum number of steps necessary to get to point $\left(d,0\right)$ on a new line.

Sample Input 0
3
2 3 1
1 2 0
3 4 11

Sample Output 0
2
0
3

Explanation 0

We perform the following $q=3$ queries:

One optimal possible path requires two steps of length $\boldsymbol{a}=2$: $(0,0)\underset{2}{\longrightarrow}(\frac{1}{2},\frac{\sqrt{15}}{2})\underset{2}{\longrightarrow}(1,0)$. Thus, we print the number of steps, $2$, on a new line.
The starting and destination points are both $(0,0)$, so we needn't take any steps. Thus, we print $\mbox{0}$ on a new line.
One optimal possible path requires two steps of length $\boldsymbol{b}=4$ and one step of length $\boldsymbol{a}=3$: $(0,0)\underset{4}{\longrightarrow}(4,0)\underset{4}{\longrightarrow}(8,0)\underset{3}{\longrightarrow}(11,0)$. Thus, we print $3$ on a new line.

Difficulty: MEDIUM
Tags: Geometry

Starter code:

Solutions:
from math import ceil

def steps(a, b, d):
	mmin = min(a, b)
	mmax = max(a, b)
	if d is 0:
		return 0
	if d in {mmin, mmax}:
		return 1
	if d < mmax:
		return 2
	return ceil(d / mmax)
t = int(input())
for testcase in range(t):
	(a, b, d) = map(int, input().split())
	print(steps(a, b, d))


q = int(input())
while q > 0:
	(a, b, d) = map(int, input().split())
	if d == 0:
		print('0')
	elif d > 0 and d < a:
		print('2')
	elif d == a:
		print('1')
	elif d > a and d < b:
		print('2')
	elif d >= b:
		print((d + b - 1) // b)
	q -= 1


num_probs = int(input())
for prob in range(num_probs):
	(a, b, d) = (int(x) for x in input().split())
	m = max(a, b)
	t = (d + m - 1) // m
	if t > 1:
		print(t)
	elif d == 0:
		print(0)
	elif d == a or d == b:
		print(1)
	else:
		print(2)


q = int(input().strip())
for _ in range(q):
	(a, b, d) = [int(c) for c in input().strip().split(' ')]
	if d == 0:
		print(0)
	elif a == d or b == d:
		print(1)
	elif d <= 2 * a or d <= 2 * b:
		print(2)
	else:
		total = d // max(a, b)
		total += 0 if total * max(a, b) == d else 1
		print(total)


def do(a, b, d):
	if d == 0:
		return 0
	elif d == a or d == b:
		return 1
	elif d < a:
		return 2
	elif d % a == 0:
		return d // a
	else:
		return d // a + 1
q = int(input().strip())
for i in range(q):
	(a, b, d) = map(int, input().strip().split())
	(a, b) = (max(a, b), min(a, b))
	rs = do(a, b, d)
	print(rs)


q = int(input().strip())
for _ in range(q):
	x = list(map(int, input().strip().split(' ')))
	(a, b, d) = (x[0], x[1], x[2])
	if d == 0:
		print(0)
	elif d % b == 0:
		print(d // b)
	elif a == d % b or d > b:
		print(d // b + 1)
	else:
		print(2)


from math import ceil
q = int(input())
for i in range(q):
	(a, b, d) = [int(x) for x in input().split(' ')]
	steps_a = ceil(d / a)
	steps_b = ceil(d / b)
	steps = min(steps_a, steps_b) if d >= a or d == 0 else 2
	if a < d < b:
		steps = 2
	print(steps)


def num_steps():
	line = input().strip().split(' ')
	step1 = int(line[0])
	step2 = int(line[1])
	max_step = max(step1, step2)
	dest = int(line[2])
	if dest == 0:
		return 0
	if dest == step1 or dest == step2:
		return 1
	if dest < max_step:
		return 2
	elif dest % max_step == 0:
		return dest // max_step
	else:
		return dest // max_step + 1
num_tests = int(input().strip())
for t in range(num_tests):
	print(num_steps())


q = int(input())
for i in range(q):
	(a, b, d) = [int(x) for x in input().split()]
	if d == 0:
		print(0)
		continue
	if d in (a, b):
		print(1)
		continue
	if d < b:
		print(2)
		continue
	steps = d // b
	leftover = d % b
	if leftover == 0:
		pass
	else:
		steps += 1
	print(steps)


q = int(input())
for i in range(q):
	(a, b, d) = [int(x) for x in input().split()]
	ans = 0
	if d != 0:
		if d == b or d == a:
			ans = 1
		elif d < b:
			ans = 2
		else:
			way_one = d // b
			if d % b:
				if d - b * (d // b) == a:
					way_one += 1
				else:
					way_one += 1
			way_two = 10000000000000000000000000
			if d % a == 0:
				way_two = d // a
			ans = min(way_one, way_two)
	print(ans)


for _ in range(int(input())):
	(a, b, d) = map(int, input().split())
	if d == 0:
		print(0)
	elif d == a or d == b:
		print(1)
	elif d < b:
		print(2)
	else:
		print((d + b - 1) // b)


import math

def check(a, b, d):
	if d == 0:
		return 0
	if d == a or d == b:
		return 1
	if d < b:
		return 2
	return math.ceil(d / b)
q = int(input().strip())
for i in range(q):
	(a, b, d) = map(int, input().strip().split())
	print(check(a, b, d))


def nsteps(a, b, d):
	if d in (a, b):
		return 1
	quotient = d // b
	if b * quotient < d:
		quotient += 1
	return quotient if quotient != 1 else 2
q = int(input())
for _ in range(q):
	(a, b, d) = [int(fld) for fld in input().strip().split()]
	print(nsteps(a, b, d))


res = []
for _ in range(int(input())):
	(a, b, d) = map(int, input().split())
	n = 0
	if d > a + b:
		n += (d - a - b) // b
		d -= n * b
	if d == a or d == b:
		n += 1
	elif d > b << 1:
		n += 3
	elif d:
		n += 2
	res.append(n)
print(*res, sep='\n')


q = int(input())
for i in range(q):
	(p, q, d) = list(map(int, input().strip().split()))
	a = max([p, q])
	b = min([p, q])
	if d == 0:
		print(0)
	elif d < b:
		print(2)
	elif d == b:
		print(1)
	elif d < a:
		print(2)
	elif d == a:
		print(1)
	elif d <= a + b:
		print(2)
	else:
		steps = 0
		while True:
			if d <= 2 * a:
				break
			d -= a
			steps += 1
		print(steps + 2)


import sys
tc_len = int(sys.stdin.readline())
for tc in range(tc_len):
	(a, b, d) = (int(x) for x in sys.stdin.readline().split())
	assert a < b
	(q, r) = divmod(d, b)
	if r == 0:
		print(q)
	elif q > 0:
		print(q + 1)
	elif r == a:
		print(q + 1)
	else:
		print(q + 2)


q = int(input())
for _ in range(q):
	(a, b, d) = map(int, input().split())
	if b > a:
		(a, b) = (b, a)
	(t, r) = divmod(d, a)
	if r and (not t):
		t = 1 if b == d else 2
	elif r:
		t += 1
	print(t)


q = int(input().strip())
for _ in range(q):
	(a, b, d) = [int(x) for x in input().strip().split()]
	x = 0
	if d == max(a, b) or d == min(a, b):
		print(1)
	elif d == 0:
		print(0)
	elif d <= 2 * max(a, b):
		print(2)
	elif max(a, b) > d:
		print(2)
	elif d % max(a, b) == 0:
		print(d // max(a, b))
	elif d % max(a, b) == min(a, b):
		print(d // max(a, b) + 1)
	else:
		print(d // max(a, b) + 1)


t = int(input())
for t1 in range(t):
	(a, b, d) = input().strip().split(' ')
	(a, b, d) = [int(a), int(b), int(d)]
	count = 0
	while True:
		if d == 0:
			print(count)
			break
		elif d == a or d == b:
			print(count + 1)
			break
		elif d < max(a, b):
			print(count + 2)
			break
		elif d < 2 * max(a, b):
			print(count + 2)
			break
		else:
			count += 1
			d -= max(a, b)


import sys

def solve(small, large, goal):
	if goal == small:
		return 1
	steps_large = goal // large
	distance_left = goal % large
	if steps_large == 0 and goal != 0:
		steps_large += 1
	if distance_left != 0:
		steps_large += 1
	return steps_large
query_count = int(input().strip())
for i in range(query_count):
	(small_size, large_size, goal) = [int(s) for s in input().strip().split()]
	print(solve(small_size, large_size, goal))


def find_ans(a, b, d):
	if not d % max(a, b):
		return d // max(a, b)
	elif not d % min(a, b):
		return d // min(a, b)
	elif d < max(a, b):
		return 2
	return d // max(a, b) + 1
for _ in range(int(input().strip())):
	(a, b, d) = map(int, input().split())
	print(find_ans(a, b, d))


def solve(a, b, d):
	if a < b:
		(a, b) = (b, a)
	if d == 0:
		return 0
	if d == b:
		return 1
	r = d // a
	if d % a != 0:
		if r == 0:
			r += 2
		else:
			r += 1
	return r
q = int(input().strip())
for i in range(q):
	(a, b, d) = input().strip().split(' ')
	a = int(a)
	b = int(b)
	d = int(d)
	print(solve(a, b, d))


def solve(a, b, d):
	ans = []
	for i in range(d // b + 1):
		j = (d - b * i) // a
		if b * i + a * j == d:
			ans.append(i + j)
	if d // b > 0:
		ans.append(d // b + 1)
	else:
		ans.append(d // b + 2)
	if d // a > 0:
		ans.append(d // a + 1)
	else:
		ans.append(d // a + 2)
	print(min(ans))
q = int(input())
for qi in range(q):
	(a, b, d) = list(map(int, input().split()))
	solve(a, b, d)


q = int(input())

def process():
	for _ in range(q):
		(a, b, d) = map(int, input().split())
		if d == 0:
			print(0)
			continue
		big = max(a, b)
		(steps, remainder) = divmod(d, big)
		if remainder == 0:
			print(steps)
		elif steps > 0:
			print(steps + 1)
		else:
			print(1 if d == a else 2)
process()


q = int(input())
for _ in range(q):
	(a, b, d) = map(int, input().split())
	if d == 0:
		print(0)
	elif d == a or d == b:
		print(1)
	elif d < b:
		print(2)
	else:
		result = d // b + (d % b > 0)
		print(result)


q = int(input())
for i in range(q):
	(a, b, d) = list(map(int, input().split()))
	coups = 0
	longueur_y = 0
	maxi = b
	if d == 0:
		coups = 0
	elif d == a or d == b:
		coups = 1
	else:
		while abs(d - longueur_y) > 2 * maxi:
			coups += 1
			longueur_y += maxi
		coups += 2
	print(coups)


for i in range(int(input())):
	[a, b, d] = list(map(int, input().strip().split()))
	if d == 0:
		print(0)
		continue
	if a >= b:
		max_length = a
		min_length = b
	else:
		max_length = b
		min_length = a
	if d < max_length:
		if d == min_length:
			print(1)
		else:
			print(2)
	elif d == max_length:
		print(1)
	else:
		[times, remainder] = divmod(d, max_length)
		if remainder == 0:
			print(times)
		else:
			if d % min_length == 0:
				min_step = d // min_length
			else:
				min_step = -1
			if (d - max_length) % min_length == 0:
				min_step1 = (d - max_length) // min_length + 1
			else:
				min_step1 = -1
			if remainder == min_length:
				print(times + 1)
			else:
				l = [times + 1]
				if min_step != -1:
					l.append(min_step)
				if min_step1 != -1:
					l.append(min_step1)
				print(min(l))


import math

def solve(a, b, d):
	steps = 0
	b2 = b * 2
	if d >= b2:
		steps += d // b2 * 2
		d = d % b2
	if d == 0:
		pass
	elif d == a:
		steps += 1
		d = 0
	else:
		steps += 2
		d = 0
	return steps

def solve2(a, b, d):
	if d == 0:
		return 0
	elif d == b:
		return 1
	elif d == a:
		return 1
	elif d < b:
		return 2
	else:
		return int(math.ceil(d / b))
q = int(input().strip())
for _ in range(q):
	(a, b, d) = [int(x) for x in input().strip().split(' ', 2)]
	print(solve2(a, b, d))


def solve(a, b, d):
	res = -1
	if d == 0:
		return 0
	(a, b) = (max(a, b), min(a, b))
	(q, r) = divmod(d, a)
	if r == 0:
		return q
	elif r == b:
		return q + 1
	elif q > 0:
		return q + 1
	else:
		return 2
	return res
q = int(input())
for i in range(q):
	(a, b, d) = map(int, input().split())
	r = solve(a, b, d)
	print(r)


q = int(input())
for x in range(q):
	(a, b, d) = [int(y) for y in input().split()]
	_max = b
	_min = a
	res = a + b
	tmp = d // b + 1
	if d % b == 0:
		print(d // b)
		continue
	elif d % a == 0:
		res = d // a
		if tmp > res:
			res = tmp
	elif d < b:
		res = 2
	else:
		for x in range(d // b - 1, 0, -1):
			if (d - b * x) % a == 0:
				res = j + (d - b * j) // a
				break
		if tmp < res:
			res = tmp
	print(res)


cases = int(input())
for i in range(0, cases):
	lineData = list(map(int, input().split(' ')))
	a = lineData[0]
	b = lineData[1]
	d = lineData[2]
	smallMoveDistance = a
	bigMoveDistance = b
	diffMoveDistance = b - a
	bigMoveCount = d // bigMoveDistance
	remainder = d - bigMoveCount * bigMoveDistance
	if d == 0:
		print(0)
	elif b > d:
		if a == d:
			print(1)
		else:
			print(2)
	elif remainder == 0:
		print(bigMoveCount)
	else:
		print(bigMoveCount + 1)


def get_answer(a, b, d):
	answer = 0
	while True:
		if d == 0:
			return answer
		if a == d or b == d:
			return answer + 1
		max_a_b = max(a, b)
		if 2 * max_a_b > d:
			return answer + 2
		else:
			d -= max_a_b
			answer += 1
q = int(input())
for _ in range(q):
	(a, b, d) = [int(x) for x in input().split()]
	print(get_answer(a, b, d))


for i in range(int(input())):
	(a, b, d) = map(int, input().split())
	s = 0
	while d:
		if d == a:
			d = 0
			s += 1
		elif d == b:
			d = 0
			s += 1
		else:
			if d <= 2 * b:
				d = 0
			else:
				d -= 2 * b
				if d < a:
					d = a
				elif d < b:
					d = b
			s += 2
	print(s)


q = int(input().strip())
for i in range(q):
	(a, b, d) = map(int, input().split())
	maxot = max(a, b)
	minot = min(a, b)
	flag = 0
	if d > maxot:
		flag = 1
	if flag == 0:
		if d == 0:
			print(0)
			continue
		elif d % maxot == 0 or d % minot == 0:
			print(1)
			continue
		else:
			print(2)
			continue
	count = d // maxot
	if d % maxot == 0:
		print(count)
	else:
		print(count + 1)


for _ in range(int(input())):
	[a, b, d] = list(map(int, input().split()))
	mx = max(a, b)
	if d == 0:
		print(0)
		continue
	if d == a or d == b:
		print(1)
		continue
	if d < mx * 2:
		print(2)
		continue
	if d % mx == 0:
		print(d // mx)
	else:
		print(d // mx + 1)


queries = int(input())
for _ in range(queries):
	(a, b, d) = map(int, input().split())
	if d == 0:
		print(0)
		continue
	if d == a or d == b:
		print(1)
		continue
	if d < b:
		print(2)
		continue
	res = d // b
	if res * b != d:
		res += 1
	print(res)


q = int(input())
abd = [input().strip().split(' ') for _ in range(q)]
abd = [[int(i) for i in line] for line in abd]
for (a, b, d) in abd:
	if d == a:
		print(1)
	elif 0 < d < b:
		print(2)
	else:
		print(-(-d // b))


t = int(input())
while t:
	t = t - 1
	xx = input().split()
	a = int(xx[0])
	b = int(xx[1])
	d = int(xx[2])
	if a > b:
		(a, b) = (b, a)
	sol = 0
	rem = d % b
	sol = d // b
	if d == 0:
		print('0')
	elif d == a:
		print('1')
	elif d == b:
		print('1')
	elif d <= b + b:
		print('2')
	elif rem == 0:
		print(sol)
	else:
		print(sol + 1)


def fun(x, y):
	if x > y:
		return [x, y]
	return [y, x]
t = int(input().strip())
while t > 0:
	t -= 1
	(a, b, d) = [int(x) for x in input().strip().split()]
	(a, b) = fun(a, b)
	if d % a == 0:
		ans = int(d / a)
	else:
		ans = int(d / a)
		if d % a == b:
			ans += 1
		else:
			extra = a - d % a
			if a != b and extra % (a - b) == 0 and (extra <= (ans + 1) * (a - b)):
				ans += 1
			else:
				ans += 2
		if d % b == 0:
			if ans > int(d / b):
				ans = int(d / b)
	tmp = int(d / a)
	if d % a != 0:
		if tmp > 0:
			tmp += 1
		else:
			tmp += 2
	if tmp < ans:
		ans = tmp
	print(ans)


from math import ceil
T = int(input())
for useless in range(T):
	(a, b, d) = map(int, input().split())
	if d == 0:
		print(0)
		continue
	if d in [a, b]:
		print(1)
		continue
	if d < 2 * b:
		print(2)
		continue
	ans = d // b
	d %= b
	ans += d != 0
	print(ans)


num_tests = int(input())
for each_test in range(num_tests):
	(a, b, dist) = map(int, input().split())
	(da, ma) = divmod(dist, a)
	(db, mb) = divmod(dist, b)
	if ma > 0:
		da = max(2, da + 1)
	if mb > 0:
		db = max(2, db + 1)
	print(min(da, db))


import sys
from math import ceil
q = input().strip()
q = int(q)
for i in range(q):
	x = [int(a_temp) for a_temp in input().strip().split(' ')]
	a = x[0]
	b = x[1]
	d = x[2]
	ans = ceil(d / b)
	if d == 0:
		print(0)
	elif d == b or d == a:
		print(1)
	elif d < b:
		print(2)
	else:
		print(ans)


T = int(input())
for _ in range(0, T):
	(a, b, d) = [int(x) for x in input().split(' ')]
	if d == 0:
		print(0)
		continue
	maxStep = max(a, b)
	minStep = min(a, b)
	minOperations = max(1, int(d / maxStep)) + 1
	if d % maxStep == 0 and int(d / maxStep) < minOperations:
		minOperations = int(d / maxStep)
	if d % minStep == 0 and int(d / minStep) < minOperations:
		minOperations = int(d / minStep)
	print(minOperations)


def min_steps(a, b, d):
	if d == 0:
		return 0
	if d == a:
		return 1
	if d % b == 0:
		return d // b
	return max(2, d // b + 1)
cases = int(input())
for case in range(cases):
	(a, b, d) = tuple(map(int, input().split()))
	print(min_steps(a, b, d))


q = int(input())
for i in range(q):
	(a, b, d) = [int(e) for e in input().split(' ')]
	if d == 0:
		print(0)
		continue
	walk = 0
	while 2 * max(a, b) < d:
		d -= max(a, b)
		walk += 1
	if d == a or d == b:
		walk += 1
	else:
		walk += 2
	print(walk)


test = int(input())
while test:
	inpu = input().split()
	a = int(inpu[0])
	b = int(inpu[1])
	d = int(inpu[2])
	reminder = d % b
	answer = d // b
	if d == 0:
		print('0')
	elif d == a:
		print('1')
	elif d == b:
		print('1')
	elif d <= b + b:
		print('2')
	elif reminder == 0:
		print(answer)
	else:
		print(answer + 1)
	test = test - 1


ts = int(input())
for t in range(ts):
	(a, b, d) = list(map(int, input().split()))
	ma = max(a, b)
	mi = min(a, b)
	if d == 0:
		count = 0
	elif d < mi:
		count = 2
	elif d == mi:
		count = 1
	elif mi < d and d < ma:
		count = 2
	else:
		c = d // ma
		d = d % ma
		if d == 0:
			count = c
		else:
			count = c + 1
	print(count)


import math
q = int(input())
for i in range(q):
	(a, b, d) = [int(x) for x in input().split()]
	if d == 0:
		print(0)
	elif d < a and d < b:
		print(2)
	else:
		ret3 = float(d) / a
		ret4 = float(d) / b
		if ret3 < 1:
			ret3 += 1
		if ret4 < 1:
			ret4 += 1
		ret5 = min(math.ceil(ret3), math.ceil(ret4))
		print(int(ret5))


def minimum_steps(a, b, d):
	if d == 0:
		return 0
	elif d == a or d == b:
		return 1
	elif 2 * b >= d:
		return 2
	else:
		if d % b == 0:
			return d // b
		return d // b + 1
t = int(input().strip())
while t > 0:
	(a, b, d) = list(map(int, input().strip().split(' ')))
	print(minimum_steps(a, b, d))
	t -= 1


from math import ceil

def solve(a, b, q):
	if q == 0:
		return 0
	if q == a or q == b:
		return 1
	if a > b:
		(a, b) = (b, a)
	return max(2, int(ceil(q / b)))
Q = int(input())
for _ in range(Q):
	(a, b, q) = map(int, input().split())
	print(solve(a, b, q))


n = int(input())
for i in range(n):
	(a, b, z) = input().split()
	a = int(a)
	b = int(b)
	z = int(z)
	c = z
	t = 0
	mn = min(a, b)
	mx = max(a, b)
	f = 0
	if c < mn:
		t = 2
	else:
		f = 1
	while c >= mn and f == 1:
		if c % mx == 0:
			t = t + int(c / mx)
			c = 0
		elif c % mn == 0:
			t = t + int(c / mn)
			c = 0
		elif c - mx > 0 and c - mx < mx:
			c = 0
			t += 2
		elif c - mx > 0:
			c = c - mx
			t += 1
		elif c - mn == 0:
			c = c - mn
			t += 1
		else:
			t += 2
			c = 0
	if z == 0:
		print(0)
	else:
		print(t)


import math

def main():
	for _ in range(int(input())):
		(a, b, d) = map(int, input().split())
		if b < a:
			(a, b) = (b, a)
		steps = 0
		if d >= b:
			steps = math.ceil(d / b)
		else:
			if d == a:
				d = 0
				steps = 1
			if d != 0:
				steps = 2
		print(steps)
main()


def hcf(u, v):
	while v > 0:
		(u, v) = (v, u % v)
	return u
q = int(input().strip())
for i in range(q):
	(a, b, d) = [int(tmp) for tmp in input().strip().split(' ')]
	if d % b == 0:
		print(d // b)
	elif d == a:
		print('1')
	else:
		print(max(1, d // b) + 1)


q = int(input())
for i in range(q):
	(a, b, d) = map(int, input().split())
	if d == 0:
		print(0)
	elif d == b:
		print(1)
	elif d == a:
		print(1)
	else:
		ans = 0
		if a > b:
			ans = d // a
			if ans == 0:
				ans += 1
			if d % a != 0:
				ans += 1
		else:
			ans = d // b
			if ans == 0:
				ans += 1
			if d % b != 0:
				ans += 1
		print(ans)


def solve(a, b, d):
	if d == a:
		return 1
	if d % b == 0:
		return d // b
	minSteps = max(d // b + 1, 2)
	return minSteps
q = int(input())
for _ in range(q):
	(a, b, d) = map(int, input().split())
	print(solve(a, b, d))


def isTriang(a, b, c):
	if a + b < c or a + c < b or b + c < a:
		return False
	else:
		return True
q = int(input())
for _ in range(q):
	(a, b, d) = list(map(int, input().split()))
	if d == 0:
		print(0)
	elif d == a or d == b:
		print(1)
	elif d < a or d < b:
		print(2)
	else:
		step = 0
		while d > 0:
			if isTriang(0, a, d):
				d -= a
			else:
				d -= b
			step += 1
		print(step)


for i0 in range(int(input())):
	(a, b, s) = [int(i) for i in input().strip().split(' ')]
	k = max(a, b)
	l = min(a, b)
	if s < 2 * k:
		if s == k or s == l:
			print(1)
		elif s == 0:
			print(0)
		else:
			print(2)
	else:
		n = s // k
		s = s % k
		if s == 0:
			print(n)
		else:
			print(n + 1)


import math
q = int(input().strip())
for _ in range(q):
	(a, b, d) = map(int, input().split())
	if d == 0:
		print('0')
	elif d == a or d == b:
		print('1')
	elif d < a or d < b:
		print('2')
	else:
		result = math.ceil(d / b)
		if (result - 2) * b + a >= d:
			print(result - 1)
		else:
			print(result)


q = int(input())
for i in range(q):
	(a, b, d) = map(int, input().split())
	if d == 0:
		print(0)
	elif d == b:
		print(1)
	elif d == a:
		print(1)
	else:
		ans = 0
		if a > b:
			ans = d // a
			if ans == 0:
				ans += 1
			if d % a != 0:
				ans += 1
		else:
			ans = d // b
			if ans == 0:
				ans += 1
			if d % b != 0:
				ans += 1
		print(ans)


import math
for _ in range(int(input())):
	step = 0
	(a, b, d) = map(int, input().split())
	while d > 0:
		if a == d or b == d:
			step += 1
			d = 0
		elif a >= math.ceil(d / 2) or b >= math.ceil(d / 2):
			step += 2
			d = 0
		else:
			d -= b
			step += 1
	print(step)


n = int(input())
for i in range(n):
	(a, b, d) = [int(x) for x in input().split()]
	res = 0
	if d % b == 0:
		print(d // b)
		continue
	if d > 2 * b:
		res += (d - b) // b
		d = d % b + b
	if d == a:
		print(res + 1)
		continue
	print(res + 2)


r = lambda : map(int, input().split())
(q,) = r()
for _ in range(q):
	(a, b, d) = r()
	if d == 0:
		print(0)
	elif d == a or d == b:
		print(1)
	else:
		c = max(a, b)
		print(max(2, (c + d - 1) // c))


def fun(a, b, d):
	if a < b:
		(a, b) = (b, a)
	if d % a == 0:
		return d // a
	ans = d // a
	d = d % a
	if d == b:
		return ans + 1
	if d + a < a + b:
		if ans != 0:
			return ans + 1
		else:
			return ans + 2
	if ans != 0:
		return ans + 1
	else:
		return ans + 2
q = int(input())
while q != 0:
	q -= 1
	(a, b, d) = [int(i) for i in input().split()]
	print(fun(a, b, d))


q = int(input())
for _ in range(q):
	(a, b, d) = [int(i) for i in input().split()]
	d2 = d
	c = 0
	if d == 0:
		print(0)
		continue
	elif d % b == 0:
		c += d // b
	else:
		f = 0
		if f == 0:
			for i in range(1, d // b + 2):
				if b * i * 2 >= d:
					m = 2 * i
					c += m
					break
		for i in range(d // b, -1, -1):
			if (d - b * i) % a == 0 and a != 1:
				f = 1
				m = i + (d - b * i) // a
				if c > m:
					c = m
				break
		(d2, t) = (d, 0)
		while d2 > 0:
			for i in range(1, d2 // b + 2):
				if b * i * 2 >= d2:
					m = 2 * i + t
					if c > m:
						c = m
					break
			t += 1
			d2 = d2 - b
	print(c)


def min_moves(a, b, d):
	if d == 0:
		return 0
	if a == d or b == d:
		return 1
	if a + b >= d:
		return 2
	ma = max(a, b)
	if d % ma == 0:
		return int(d / ma)
	else:
		return d // ma + 1
q = int(input().strip())
for i in range(q):
	(a, b, d) = tuple(map(int, input().strip().split(' ')))
	print(min_moves(a, b, d))


from math import ceil

def min_steps(a, b, d):
	if d == 0:
		return 0
	elif d == a or d == b:
		return 1
	elif d <= a + b:
		return 2
	else:
		larger = max(a, b)
		return ceil(d / larger)
q = int(input())
for _ in range(q):
	(a, b, d) = list(map(int, input().strip().split()))
	print(min_steps(a, b, d))


import math
(a, b, d) = (3, 4, 11)

def calc(a, b, d):
	if d == 0:
		return 0
	else:
		_a = max(a, b)
		_b = min(a, b)
		if d % _a == 0:
			return int(d / _a)
		else:
			ahead_count = math.floor(d / _a)
			tail_min = d - math.floor(d / _a) * _a
			tail_max = d
			if _a >= tail_min and _a <= tail_max or (_b >= tail_min and _b <= tail_max):
				return ahead_count + 1
			else:
				return ahead_count + 2
q = int(input().strip())
for i in range(q):
	(a, b, d) = [int(i) for i in input().strip().split(' ')]
	print(calc(a, b, d))


q = int(input())
for x in range(q):
	inp = [int(i) for i in input().split(' ')]
	(a, b, d) = (inp[0], inp[1], inp[2])
	(aa, bb, dd) = (a, b, d)
	if d == 0:
		print(0)
	elif d == a or d == b:
		print(1)
	elif a + b >= d and a + d >= b and (b + d >= a) or (a + a >= d and d + a >= a) or (b + b >= d and d + b >= b):
		print(2)
	else:
		steps = 2
		while a + b < d or a + d < b or b + d < a:
			if a + aa >= d and a + d >= aa and (aa + d > a) or (b + bb >= d and b + d >= bb and (bb + d >= b)):
				break
			if a + d < b:
				a = a + aa
				steps += 1
			elif b + d < a:
				b = b + bb
				steps += 1
			elif a + b < d:
				b = b + bb
				steps += 1
		print(steps)


Q = int(input())
for q in range(Q):
	(a, b, d) = input().split(' ')
	(a, b, d) = (int(a), int(b), int(d))
	if d == 0:
		print(0)
	elif d == a or d == b:
		print(1)
	elif d <= 2 * b:
		print(2)
	elif d % b == 0:
		print(d // b)
	else:
		print(d // b + 1)


def count_moves(a, b, distance):
	if distance == 0:
		return 0
	if distance == a or distance == b:
		return 1
	moves = 0
	while distance > 2 * b:
		moves += 1
		distance -= b
	if distance == a or distance == b:
		return moves + 1
	else:
		return moves + 2
cases = []
q = int(input().strip())
for _ in range(q):
	(a, b, d) = [int(x) for x in input().strip().split()]
	cases.append((a, b, d))
a = 0
b = 1
d = 2
for c in cases:
	moves = count_moves(c[a], c[b], c[d])
	print(moves)


def minSteps(a, b, d):
	if d == 0:
		return 0
	if d == a or d == b:
		return 1
	if d % b == 0:
		return d // b
	return max(2, d // b + 1)
q = int(input().strip())
for _ in range(q):
	(a, b, d) = map(int, input().strip().split())
	print(minSteps(a, b, d))


q = int(input())
for i in range(q):
	(a, b, d) = map(int, input().split())
	if d == 0:
		steps = 0
	else:
		steps = d // b
		rest = d % b
		if steps == 0:
			if rest == a:
				steps = 1
			else:
				steps = 2
		elif rest != 0:
			steps += 1
	print(steps)


import math
for i in range(int(input())):
	s = 0
	(a, b, d) = map(int, input().split())
	while d > 0:
		if a == d or b == d:
			s = s + 1
			break
		elif a >= math.ceil(d / 2) or b >= math.ceil(d / 2):
			s = s + 2
			break
		else:
			d = d - b
			s = s + 1
	print(s)


import math
q = int(input())
for i in range(q):
	(a, b, d) = [int(s) for s in input().split()]
	if d == 0:
		print(0)
	else:
		step = 0
		while d > 2 * max(a, b):
			step += 1
			d = d - max(a, b)
		if d == a or d == b:
			step += 1
		else:
			step += 2
		print(step)


for q in range(int(input().strip())):
	(n, m, d) = map(int, input().strip().split())
	if d == 0:
		print(0)
	elif d in [n, m]:
		print(1)
	elif max(n * 2, m * 2) > d:
		print(2)
	else:
		_max = max(n, m)
		big_steps = d // _max
		if d - big_steps * _max == 0:
			print(big_steps)
		else:
			print(big_steps + 1)


for _ in range(int(input())):
	(a, b, d) = map(int, input().split())
	c = d // b
	d %= b
	if d:
		if c:
			c += 1
		elif d % a == 0:
			c += 1
		else:
			c += 2
	print(c)


q = int(input())
for _ in range(q):
	(a, b, d) = map(int, input().split())
	longer = max(a, b)
	shorter = min(a, b)
	if d == 0:
		res = 0
	elif d == shorter or d == longer:
		res = 1
	elif d < longer:
		res = 2
	else:
		res = d // longer
		res += bool(d % longer)
	print(res)


q = int(input())
for _ in range(q):
	(a, b, d) = [int(x) for x in input().split()]
	ans = 0
	if d == 0:
		ans = 0
	elif d < a:
		ans = 2
	elif d == a:
		ans = 1
	elif d < b:
		ans = 2
	elif d % b == 0:
		ans = d // b
	else:
		ans = d // b + 1
	print(ans)


import sys
for i in range(int(input().strip())):
	(a, b, d) = map(int, input().strip().split())
	if d == a:
		print(1)
	elif 0 < d < b:
		print(2)
	else:
		print(d // b + (d % b != 0))


q = int(input().strip())
for i in range(q):
	(a, b, d) = [int(n) for n in input().strip().split(' ')]
	n_move = 0
	if d == 0:
		n_move = 0
	elif d == a:
		n_move = 1
	elif d < b:
		n_move = 2
	else:
		n_move = d // b
		n_remain = d % b
		if n_remain != 0:
			n_move += 1
	print(n_move)


Q = int(input())

def fstep(arr):
	if arr[2] == 0:
		return 0
	elif arr[2] == arr[0] or arr[2] == arr[1]:
		return 1
	else:
		return 2

def step(arr):
	count_1 = 0
	count = 0
	if arr[2] % arr[0] == 0:
		return int(arr[2] / arr[0])
	elif arr[2] % arr[1] == 0:
		return int(arr[2] / arr[1])
	else:
		st = arr[2] // arr[1]
		for i in range(1, st):
			if arr[0] <= arr[2] - (st - i) * arr[1] <= 2 * arr[1]:
				count = st - i + 2
				return count
		count += arr[2] // arr[1] + fstep(arr1)
		return count
for _ in range(Q):
	arr = list(map(int, input().split(' ')))
	if arr[2] <= 2 * arr[1]:
		print(fstep(arr))
	else:
		print(step(arr))


queries = int(input())
for q in range(queries):
	(a, b, d) = [int(x) for x in input().split()]
	if d == 0:
		print(0)
	elif d // b == 1 and d % b == 0 or (d // a == 1 and d % a == 0):
		print(1)
	else:
		steps_needed = d // b
		if d % b != 0:
			steps_needed += 1
			if steps_needed == 1:
				steps_needed += 1
		print(steps_needed)


q = int(input())
res = []
for i in range(q):
	(a, b, d) = [int(j) for j in input().split(' ')]
	if d == 0:
		res.append(0)
		continue
	elif d == a or d == b:
		res.append(1)
		continue
	elif d < a or d < b:
		res.append(2)
		continue
	elif d % b == 0:
		res.append(d // b)
		continue
	else:
		res.append(d // b + 1)
for i in range(q):
	print(res[i])


import sys

def min_steps(small_step_size, big_step_size, destination):
	if destination == 0:
		return 0
	steps = destination // big_step_size
	remainder = destination % big_step_size
	if not remainder:
		return steps
	if remainder == small_step_size:
		return steps + 1
	if steps == 0:
		return 2
	return steps + 1

def main(sinp=sys.stdin, sout=sys.stdout):
	n = map(int, sinp.readline().split())
	results = []
	for line in sinp:
		(a, b, d) = map(int, line.split())
		results.append(min_steps(a, b, d))
	sout.write('\n'.join(map(str, results)))
main()


q = int(input())
for _ in range(q):
	(a, b, d) = [int(x) for x in input().strip().split()]
	big_steps = d // b
	if d % b == 0:
		print(big_steps)
	elif big_steps == 0:
		if d == a:
			print(1)
		else:
			print(2)
	else:
		print(big_steps + 1)


import sys

def solve(a, b, d):
	big_step = max(a, b)
	small_step = min(a, b)
	big_step_no = d // big_step
	current_position = big_step_no * big_step
	if current_position == d:
		return big_step_no
	if current_position + a == d:
		return big_step_no + 1
	diff = big_step - small_step
	if 0 != diff and 0 != current_position and (current_position + small_step > d) and ((current_position + small_step - d) // diff <= big_step_no):
		return big_step_no + 1
	if 0 == big_step_no:
		return big_step_no + 2
	return big_step_no + 1
q = int(input().strip())
for i in range(0, q):
	(a, b, d) = [int(temp) for temp in input().strip().split(' ')]
	print(solve(a, b, d))


def gm(a, b, d):
	if d == 0:
		return 0
	if d == a or d == b:
		return 1
	if d < b:
		return 2
	m = 0
	m = d // b
	d -= b * m
	if d == 0:
		return m
	if d == a:
		return m + 1
	d += b
	if d < 2 * b:
		return m + 1
	return m + 2
q = int(input())
for _ in range(q):
	(a, b, d) = map(int, input().strip().split(' '))
	if b < a:
		(a, b) = (b, a)
	print(gm(a, b, d))


import sys
q = int(sys.stdin.readline())
for i in range(q):
	(a, b, d) = map(int, sys.stdin.readline().split())
	if d % b == 0:
		print(d // b)
	elif d == a:
		print(1)
	else:
		print(max(2, d // b + 1))


q = int(input().strip())
for i in range(q):
	(a, b, d) = map(int, input().split())
	if d <= b:
		print((d == 0) * 0 + (d == b or d == a) * 1 + (d != 0 and d != a and (d < b)) * 2)
	elif d % b == 0:
		print(d // b)
	elif d % b % a == 0 and d % b // a == 1:
		print(d // b + 1)
	else:
		print((d - 2 * b) // b + 3)


q = int(input())

def step(a, b, d):
	step = 0
	extra = 0
	if d > 2 * max(a, b):
		extra = d // max(a, b) - 1
		d = d - extra * max(a, b)
	step = step_small(a, b, d) + extra
	return step

def step_small(a, b, d):
	if d == 0:
		step = 0
	elif d == a or d == b:
		step = 1
	else:
		step = 2
	return step
for i in range(q):
	(a, b, d) = map(int, input().split())
	step_min = step(a, b, d)
	print(step_min)


q = int(input())
for tc in range(q):
	(a, b, d) = map(int, input().split())
	if d % b == 0:
		print(d // b)
	elif d % b == a:
		print(d // b + 1)
	elif d - b < 0:
		if d % a == 0:
			print(min(d // a), 2)
		else:
			print(2)
	else:
		print((d - b) // b + 2)


import sys
import math

def linear_diophantine(a, b, c):
	print('%dx+%dy=%d' % (a, b, c), file=sys.stderr)
	if c == 0:
		return None
	(p, q, r, t) = (a, a // b, b, a % b)
	cache = [(p, q, r, t)]
	print('p=%d q=%d r=%d t=%d' % (p, q, r, t), file=sys.stderr)
	while t:
		(p, q, r, t) = (r, r // t, t, r % t)
		cache.append((p, q, r, t))
		print('p=%d q=%d r=%d t=%d' % (p, q, r, t), file=sys.stderr)
	(G, R) = (cache[-1][2], cache[-2][-1])
	(e, f, g, h) = (1, cache[-2][0], -cache[-2][1], cache[-2][2])
	for i in range(len(cache) - 3, -1, -1):
		print('(%d) * %d + (%d) * %d = %d' % (e, f, g, h, R), file=sys.stderr)
		(p, q, r, t) = cache[i]
		(e, f, g, h) = (g, p, e - g * q, f)
	print('(%d) * %d + (%d) * %d = %d' % (e, f, g, h, R), file=sys.stderr)
	(u, v) = (c // R, c % R)
	return (e * u, g * u, G, v)

def solve_old(a, b, d):
	if d == 0:
		return 0
	(x0, y0, g, R) = linear_diophantine(a, b, d)
	(a1, b1) = (a // g, b // g)
	print('%d*x+%d*y=%d g=%d' % (a, b, d - R, g), file=sys.stderr)
	print('x=(%d)+(%d)t y=(%d)+(%d)t' % (x0, b1, y0, -a1), file=sys.stderr)
	t = (b * y0 - d) / (a1 * b)
	ti = math.ceil(t)
	y = y0 - a1 * ti
	if b * y < d:
		ti -= 1
		y += a1
	print('t=%s ti=%d ymax=%d b*ymax=%d' % (t, ti, y, b * y), file=sys.stderr)
	if y == 0:
		x = x0 + b1 * ti
		return x
	if b * y > d:
		return y
	elif b * y < d:
		return y + 1
	else:
		return y

def solve(a, b, d):

	def steps(c, d):
		(s, r) = (d // c, d % c)
		if r == 0:
			return s
		if s == 0:
			return 2
		return s + 1
	(sa, sb) = (steps(a, d), steps(b, d))
	print('a=%d b=%d d=%d sa=%d sb=%d' % (a, b, d, sa, sb), file=sys.stderr)
	return min(sa, sb)
t = int(input())
for _ in range(t):
	(a, b, d) = map(int, input().split())
	print(solve(a, b, d))


q = int(input())
for a0 in range(q):
	(a, b, d) = map(int, input().split())
	steps = 1
	d1 = d
	if d == 0:
		print('0')
	elif d == a or d == b:
		print(steps)
	else:
		while True:
			steps = steps + 1
			if a + a >= d or a + b >= d or b + b >= d:
				break
			else:
				d = d - b
		print(steps)


q = int(input())
for x in range(q):
	(a, b, d) = [int(var) for var in input().strip().split(' ')]
	if d == 0:
		print(0)
		continue
	if d == a or d == b:
		print(1)
		continue
	if d < 2 * b:
		print(2)
		continue
	steps = (d - 2 * b) // b
	if d - steps * b > 2 * b:
		steps += 1
	if d - steps * b == a:
		steps += 1
	else:
		steps += 2
	print(steps)


from math import ceil
for each in range(int(input().strip())):
	(a, b, d) = [int(i) for i in input().strip().split(' ')]
	if d < b + b:
		if d == 0:
			print(0)
		elif d == a or d == b:
			print(1)
		else:
			print(2)
	else:
		d1 = d
		d1 = d1 - (b + b)
		ans = ceil(d1 / b)
		d = d - (ans - 1) * b
		if d == 0:
			ans += 0
		elif d == a or d == b:
			ans += 1
		else:
			ans += 2
		print(ans)


def helper(a, b, d):
	if d == 0:
		return 0
	if a < b:
		temp = a
		a = b
		b = temp
	if d == b:
		return 1
	step = d // a
	left = d % a
	if step == 0:
		return 2
	if left == 0:
		return step
	else:
		return step + 1
q = int(input())
for _ in range(q):
	(a, b, d) = map(int, input().split())
	print(helper(a, b, d))


import math
for _ in range(int(input())):
	(a, b, d) = map(int, input().split())
	if d == 0:
		print(0)
	elif a == d:
		print(1)
	else:
		steps = math.ceil(d / b)
		if steps * b > d and steps == 1:
			steps += 1
		print(steps)


from math import ceil
q = int(input().strip())
for _ in range(q):
	(a, b, d) = list(map(int, input().strip().split()))
	abmax = max(a, b)
	ret = 0
	if d == 0:
		ret = 0
	elif d == a or d == b:
		ret = 1
	elif abmax > d:
		ret = 2
	else:
		ret = ceil(d / abmax)
	print(ret)