Monocarp is playing a MMORPG. There are two commonly used types of currency in this MMORPG — gold coins and silver coins. Monocarp wants to buy a new weapon for his character, and that weapon costs $n$ silver coins. Unfortunately, right now, Monocarp has no coins at all.

Monocarp can earn gold coins by completing quests in the game. Each quest yields exactly one gold coin. Monocarp can also exchange coins via the in-game trading system. Monocarp has spent days analyzing the in-game economy; he came to the following conclusion: it is possible to sell one gold coin for $a$ silver coins (i. e. Monocarp can lose one gold coin to gain $a$ silver coins), or buy one gold coin for $b$ silver coins (i. e. Monocarp can lose $b$ silver coins to gain one gold coin).

Now Monocarp wants to calculate the minimum number of quests that he has to complete in order to have at least $n$ silver coins after some abuse of the in-game economy. Note that Monocarp can perform exchanges of both types (selling and buying gold coins for silver coins) any number of times.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of one line containing three integers $n$, $a$ and $b$ ($1 \le n \le 10^7$; $1 \le a, b \le 50$).


-----Output-----

For each test case, print one integer — the minimum possible number of quests Monocarp has to complete.


-----Examples-----

Input
4
100 25 30
9999997 25 50
52 50 48
49 50 1
Output
4
400000
1
1


-----Note-----

In the first test case of the example, Monocarp should complete $4$ quests, and then sell $4$ gold coins for $100$ silver coins.

In the second test case, Monocarp should complete $400000$ quests, and then sell $400000$ gold coins for $10$ million silver coins.

In the third test case, Monocarp should complete $1$ quest, sell the gold coin for $50$ silver coins, buy a gold coin for $48$ silver coins, and then sell it again for $50$ coins. So, he will have $52$ silver coins.

In the fourth test case, Monocarp should complete $1$ quest and then sell the gold coin he has obtained for $50$ silver coins.

Difficulty: EASY
Tags: Mathematics

Complete search
Skill types: Complete search

Starter code:

Solutions:
from collections import *
from itertools import permutations
import sys
import math
sys.setrecursionlimit(10 ** 5)
itr = (line for line in sys.stdin.read().split('\n'))
INP = lambda : next(itr)

def ni():
	return int(INP())

def nl():
	return [int(_) for _ in INP().split()]

def err(*s):
	print(*s, file=sys.stderr)

def pl(a):
	print(' '.join(map(str, a)))

def solve(n, a, b):
	if a > b:
		return 1
	else:
		return math.ceil(n / a)

def main():
	t = ni()
	for _ in range(t):
		(n, a, b) = nl()
		print(solve(n, a, b))
main()


import sys
input = sys.stdin.readline
import math

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

def print_number(number):
	print_str_line(f'{number}')

def ans(n, a, b):
	if a > b:
		return 1
	ans = math.ceil(n / a)
	return ans
number_of_test_cases = int(input())
for i in range(number_of_test_cases):
	(n, a, b) = [int(num) for num in input().split(' ')]
	_ans = ans(n, a, b)
	print_number(_ans)


import sys
s = sys.stdin.read()
lines = s.split('\n')
import math

def solve(a, b, c):
	if c < b:
		print(1)
		return
	result = math.ceil(a / b)
	print(result)
for line in lines[1:-1]:
	(a, b, c) = map(int, line.split())
	solve(a, b, c)


import sys
s = sys.stdin.read()
lines = s.split('\n')
import math

def memorize(func):
	cache = {}

	@wraps(func)
	def wrapper(*args, **kwargs):
		key = str(args) + str(kwargs)
		if key not in cache:
			cache[key] = func(*args, **kwargs)
		return cache[key]
	return wrapper

def cal_ceil(a, b):
	return math.ceil(a / b)

def solve(a, b, c):
	if c < b:
		print(1)
		return
	result = cal_ceil(a, b)
	print(result)
for line in lines[1:-1]:
	(a, b, c) = map(int, line.split())
	solve(a, b, c)


import sys, math
rd = sys.stdin.readline
for _ in range(int(rd())):
	(n, a, b) = map(int, rd().split())
	if a > b:
		print(1)
	else:
		print(math.ceil(n / a))


import math

def ans(n, a, b):
	if b >= a:
		r = int(math.ceil(n / a))
		return r
	else:
		return 1
t = int(input())
l = []
for i in range(t):
	(n, a, b) = map(int, input().split())
	l.append(ans(n, a, b))
for i in range(t):
	print(l[i])


import sys
input = sys.stdin.readline
t = int(input())
while t > 0:
	(n, a, b) = map(int, input().split())
	if a > b:
		print(1)
	else:
		print(int((n + a - 1) / a))
	t -= 1


samples = [*open(0)]
count = samples[0]
i = 1
while i < len(samples):
	[n, a, b] = samples[i].split(' ')
	if int(a) > int(b):
		print(1)
	else:
		n = int(n) / int(a) + (int(n) % int(a) > 0)
		print(int(n))
	i += 1


import sys
from os import path

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

def solve(n, a, b):
	(q, r) = (n // a, n % a)
	if a > b:
		print(1)
	elif q and (not r):
		print(q)
	elif q and bool(r):
		print(q + 1)
	elif not q:
		print(1)

def main():
	testcases = int(input())
	for _ in range(testcases):
		(n, a, b) = map(int, input().split())
		solve(n, a, b)
if path.exists('Tests'):
	sys.stdin = open('Tests/input_1.txt', 'r')
	sys.stdout = open('Tests/output_1a.txt', 'w')
main()


def exchange_rates(lyst):
	val = lyst[0]
	gold_to_silver = lyst[1]
	silver_to_gold = lyst[2]
	if val <= gold_to_silver or gold_to_silver > silver_to_gold:
		return 1
	elif val / gold_to_silver % 1 == 0:
		return int(val / gold_to_silver)
	else:
		return int(val / gold_to_silver) + 1

def printer(lyst):
	for i in range(len(lyst)):
		print(lyst[i])
final_list = []
cases = int(input())
for _ in range(cases):
	arr = list(input().split(' '))
	for j in range(len(arr)):
		arr[j] = int(arr[j])
	final_list.append(exchange_rates(arr))
printer(final_list)


t = int(input())
out = []
for i in range(t):
	(n, a, b) = map(int, input().split())
	if a > b:
		out.append(1)
	else:
		out.append(n // a + bool(n % a))
for k in out:
	print(k)


t = int(input())
prin = []
for i in range(t):
	(n, a, b) = input().split()
	(n, a, b) = (int(n), int(a), int(b))
	if a - b <= 0:
		q = int(n / a)
		if n % a == 0:
			prin.append(q)
		else:
			prin.append(q + 1)
	else:
		prin.append(1)
for i in prin:
	print(i)


test_case = int(input())
ans = []
for i in range(test_case):
	(n, s, b) = input().split()
	if int(s) >= int(n):
		ans.append(1)
	elif int(s) <= int(b):
		if int(n) % int(s) == 0:
			ans.append(int(n) // int(s))
		else:
			ans.append(int(n) // int(s) + 1)
	else:
		ans.append(1)
for i in range(test_case):
	print(ans[i])


from sys import stdin

def main():
	for _ in range(int(stdin.readline().strip())):
		(n, a, b) = list(map(int, stdin.readline().strip().split()))
		print(exchange(n, a, b))

def exchange(n, a, b):
	if a > b:
		return 1
	else:
		return n // a + (n % a != 0)
main()


from math import ceil
n = int(input())
results = []
for i in range(n):
	nums = input()
	nums = nums.split()
	nums = list(map(lambda x: int(x), nums))
	if nums[1] > nums[2]:
		results.append(1)
	elif nums[1] <= nums[2]:
		ans = nums[0] / nums[1]
		results.append(ceil(ans))
for item in results:
	print(item)


from math import ceil
cases = int(input())
inp = []
for _ in range(cases):
	inp.append([int(x) for x in input().split(' ')])
for x in inp:
	if x[1] > x[2]:
		print(1)
	else:
		print(ceil(x[0] / x[1]))


import math
t = int(input(''))
A = []
for i in range(t):
	(n, a, b) = [int(p) for p in input('').split()]
	A.append([n, a, b])
for i in range(t):
	arr = A[i]
	if arr[1] > arr[2]:
		print(1)
	else:
		print(math.ceil(arr[0] / arr[1]))


t = int(input())
for i in range(t):
	(n, a, b) = map(int, input().split())
	if a <= b:
		print(-(-n // a))
	else:
		print(1)


for _ in '0' * int(input()):
	(n, a, b) = map(int, input().split())
	print(1 if a > b else n // a + (n % a != 0))


t = int(input())
import math
while t > 0:
	(n, a, b) = input().split()
	(n, a, b) = (int(n), int(a), int(b))
	if b < a:
		print(1)
	else:
		print(math.ceil(n / a))
	t -= 1


from math import ceil
for ijij in range(int(input())):
	(n, a, b) = map(int, input().split())
	if a <= b:
		print(ceil(n / a))
	else:
		print(1)


import math
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	if a <= b:
		ans = math.ceil(n / a)
	else:
		ans = 1
	print(ans)


def sol(n, g, s):
	if s >= g:
		if n % g != 0:
			return n // g + 1
		return n // g
	return 1
for _ in range(int(input())):
	a = input().split()
	print(sol(int(a[0]), int(a[1]), int(a[2])))


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	print(1 if b > c else (a + b - 1) // b)


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


import math as kim
n = int(input())
for _ in range(n):
	(n, a, b) = [int(i) for i in input().split()]
	if a > b:
		print(1)
	else:
		t = kim.ceil(n / a)
		print(t)


from math import ceil
for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	if b > c:
		print(1)
	else:
		print(ceil(a / b))


tests = int(input())
for _ in range(tests):
	(n, a, b) = list(map(int, input().split()))
	if a > b:
		print(1)
	else:
		print(n // a + (1 if n % a else 0))


import sys
t = int(input())
for _ in range(t):
	nab = [int(ii) for ii in input().split()]
	(n, a, b) = (nab[0], nab[1], nab[2])
	if b < a:
		print(1)
	else:
		print((n - 1) // a + 1)


import math
t = int(input())
for i in range(t):
	(n, a, b) = map(int, input().split())
	count = 0
	if a < b:
		count = math.ceil(n / a)
	elif a > b:
		count = 1
	elif a == b:
		count = math.ceil(n / a)
	print(count)


import math

def solve(n, a, b):
	argent = 0
	mission = 0
	if a <= b:
		mission = math.ceil(n / a)
	else:
		mission += 1
	return mission

def test():
	t = int(input())
	for j in range(t):
		(n, a, b) = [int(x) for x in input().split()]
		print(solve(n, a, b))
test()


import math
for i in range(int(input())):
	(n, a, b) = map(int, input().split())
	m = n // a
	if a <= b:
		print(int(math.ceil(n / a)))
	else:
		print(1)


T = int(input())
for i in range(T):
	(n, a, b) = list(map(int, input().split()))
	k = n // a
	if a >= n or (b < a and a < n):
		print(1)
	elif b >= a:
		if n % a == 0:
			print(k)
		else:
			print(k + 1)


import math

def monocarp(n, a, b):
	if n == 0:
		return 0
	elif a > b:
		return 1
	else:
		return math.ceil(n / a)
t = int(input())
for i in range(t):
	lis = list(map(int, input().split()))
	print(monocarp(lis[0], lis[1], lis[2]))


for i in range(int(input())):
	line = input().split(' ')
	n = int(line[0])
	a = int(line[1])
	b = int(line[2])
	if a > b:
		print(1)
	else:
		print((n - 1) // a + 1)


import math
num = int(input())
for j in range(num):
	txt = input()
	x = txt.split()
	n = int(x[0])
	a = int(x[1])
	b = int(x[2])
	if a <= b:
		quest = math.ceil(n / a)
		print(quest)
	else:
		print(1)


def main():
	al = int(input())
	for i in range(al):
		(n, a, b) = [int(x) for x in input().split()]
		if a > b:
			print(1)
		else:
			print((n + a - 1) // a)
main()


t = int(input())
for tests in range(t):
	(p, a, b) = map(int, input().split())
	if a > b:
		print(1)
	elif p % a == 0:
		print(p // a)
	else:
		print(p // a + 1)


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	if a > b:
		print(1)
	else:
		res1 = (n + a - 1) // a
		print(res1)


test_cases = int(input())
for _ in range(test_cases):
	(n, a, b) = map(int, input().split())
	quests = 0
	if a > b:
		print(1)
	else:
		temp = n // a
		if n % a != 0:
			temp += 1
		print(temp)


num_of_cases = int(input())
for case in range(num_of_cases):
	(n, a, b) = map(int, input().split())
	if a > b:
		print(1)
	else:
		print((n - 1) // a + 1)


for t in range(int(input())):
	(n, a, b) = list(map(int, input().split()))
	if b < a:
		print(1)
		continue
	r = n // a
	if r == n / a:
		print(r)
	else:
		print(r + 1)


import math

def solve(n, a, b):
	res = 1
	if a <= b:
		res = math.ceil(n / a)
	print(res)
t = int(input())
for _ in range(t):
	(n, a, b) = map(int, input().split())
	solve(n, a, b)


import math

def solve():
	[n, a, b] = [int(num) for num in input().split()]
	if b < a:
		print(1)
	else:
		quests = n / a
		print(math.ceil(quests))
for _ in range(int(input())):
	solve()


import math
t = int(input())
quests = 0
s_coins = 0
for i in range(t):
	quests = 0
	(n, a, b) = map(int, input().split())
	quests = math.ceil(n / a)
	if a > b:
		quests = 1
		pass
	print(quests)


import math
t = int(input())
for test in range(t):
	(n, a, b) = map(int, input().split())
	if a <= b:
		x = math.ceil(n / a)
	else:
		x = 1
	print(x)


t = int(input())
for i in range(t):
	inp = list(map(int, input().split()))
	n = inp[0]
	a = inp[1]
	b = inp[2]
	if a > b:
		print('1')
	elif n % a != 0:
		print(str(int(n / a) + 1))
	else:
		print(str(int(n / a)))


def solve(N, A, B) -> int:
	if B < A:
		return 1
	return (N + A - 1) // A

def run_test_case() -> None:
	(N, A, B) = list(map(int, input().split()))
	print(solve(N, A, B))

def main():
	T = int(input())
	while T > 0:
		T -= 1
		run_test_case()
main()


t = int(input())
for _ in range(t):
	(n, a, b) = list(map(int, input().split()))
	if a > b:
		print(1)
	else:
		print(-(-n // a))


from math import ceil

def func(n, a, b):
	if a > b:
		return 1
	return ceil(n / a)

def main():
	t = int(input())
	for i in range(t):
		(n, a, b) = map(int, input().split())
		print(func(n, a, b))
main()


for i in range(int(input())):
	(n, a, b) = map(int, input().split())
	print([(n - 1) // a + 1, 1][a > b or a >= n])


from math import ceil
t = int(input())
for _ in range(t):
	(total, a, b) = (int(i) for i in input().split(' '))
	if a > b:
		print(1)
	else:
		print(int(ceil(total / a)))


for _ in range(int(input())):
	(n, a, b) = map(int, input().strip().split())
	if a <= b:
		quests_no = -(-n // a)
	else:
		quests_no = 1
	print(quests_no)


import math
t = int(input())
while t > 0:
	(n, a, b) = [int(x) for x in input().split(' ')]
	if b < a:
		print(1)
	else:
		x = math.ceil(n / a)
		print(x)
	t -= 1


t = int(input())
for t1 in range(t):
	(n, a, b) = map(int, input().split())
	if a > b:
		print(1)
	elif n % a == 0:
		print(n // a)
	else:
		print(1 + n // a)


t = int(input())
for _ in range(t):
	(n, a, b) = map(int, input().split())
	if a > b:
		print(1)
	else:
		x = n // a
		m = n % a
		if m == 0:
			print(x)
		else:
			print(x + 1)


def gold(n, a, b):
	if a > n:
		return 1
	elif a <= b:
		if n % a > 0:
			return int(n / a) + 1
		else:
			return int(n / a)
	elif b < a:
		return 1
tc = int(input())
for i in range(tc):
	(a, b, c) = map(int, input().split())
	print(gold(a, b, c))


import os, sys, io, math
from array import *
from math import *
from bisect import *
from heapq import *
from functools import *
from itertools import *
from collections import *
I = lambda : [*map(int, sys.stdin.readline().split())]
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())
for _ in range(IN()):
	(n, a, b) = map(int, input().split())
	print(1 if a > b else ceil(n / a))


import math

def exchange(goal, g_to_s, s_to_g):
	if g_to_s > s_to_g:
		return 1
	else:
		return math.ceil(goal / g_to_s)
for _ in range(int(input())):
	(goal, g_to_s, s_to_g) = map(int, input().split())
	print(exchange(goal, g_to_s, s_to_g))


import math
import sys

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

def solve():
	inputString = input()
	lst = list(map(int, inputString.split()))
	n = lst[0]
	a = lst[1]
	b = lst[2]
	if b < a:
		print(1)
	else:
		c = math.ceil(n / a)
		print(c)
t = int(input())
while t > 0:
	solve()
	t -= 1


import math
t = int(input())
for k in range(t):
	(n, a, b) = (int(x) for x in input().split())
	if b >= a:
		answer = math.ceil(n / a)
	else:
		answer = 1
	print(answer)


for jj in range(int(input())):
	(n, a, b) = [int(i) for i in input().split()]
	if a > b:
		print(1)
	else:
		print((n - 1) // a + 1)


T = int(input())
for t in range(T):
	(n, a, b) = map(int, input().strip().split())
	if a <= b:
		print(int(n / a) + (n % a != 0))
	else:
		print(int(b / a) + (b % a != 0))