In a country called Chef Land, there was a lot of monetary fraud, so Chefu, the head of the country, decided to choose new denominations of the local currency ― all even-valued coins up to an integer $N$ should exist. After a few days, a citizen complained that there was no way to create an odd value, so Chefu decided that he should also introduce coins with value $1$. Formally, you are given an integer $N$; for $v = 1$ and each even positive integer $v \le N$, coins with value $v$ exist.
You are also given an integer $S$. To handle transactions quickly, find the minimum number of coins needed to pay a price $S$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first and only line of each test case contains two space-separated integers $S$ and $N$.

-----Output-----
For each test case, print a single line containing one integer ― the minimum number of coins.

-----Constraints-----
- $1 \le T \le 10,000$
- $1 \le S \le 10^9$
- $2 \le N \le 10^9$
- $N$ is even

-----Subtasks-----
Subtask #1 (100 points): original constraints

-----Example Input-----
4
2 2
1 14
30 10
31 4

-----Example Output-----
1
1
3
9

-----Explanation-----
Example case 1: One coin with value $2$ is sufficient.
Example case 2: We need to use one coin with value $1$.
Example case 3: We need $3$ coins, each with value $10$.
Example case 4: We can use seven coins with value $4$, one coin with value $2$ and one coin with value $1$.

Difficulty: EASY
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
a = int(input(''))
for i in range(a):
	(S, N) = [int(x) for x in input('').split()]
	h = S % N
	if h == 1 or (h % 2 == 0 and h != 0):
		print(S // N + 1)
	elif h == 0:
		print(S // N)
	else:
		print(S // N + 2)


t = int(input())
for _ in range(t):
	(s, n) = map(int, input().split())
	if s <= n and s % 2 == 0 or s == 1:
		print(1)
	elif s < n:
		print(2)
	else:
		coin = 0
		while s > n:
			coin = coin + s // n
			s = s % n
		if s == 0:
			print(coin)
		elif s == 1 or s % 2 == 0:
			print(coin + 1)
		else:
			print(coin + 2)


for _ in range(int(input())):
	(S, N) = map(int, input().split())
	c = S // N
	S %= N
	if S > 0:
		c += 2 if S % 2 and S > 1 else 1
	print(c)


t = int(input())
for i in range(0, t):
	count = 0
	(s, n) = map(int, input().split())
	while s > 0:
		count = count + s // n
		s = s % n
		if s >= 2:
			if s % 2 == 0:
				n = s
			else:
				n = s - 1
		else:
			n = 1
	print(count)


t = int(input())
for i in range(0, t):
	coin = 0
	(s, n) = map(int, input().split())
	rem = s % n
	if s == 1:
		coin = coin + s
	elif rem == 0:
		z = int(s / n)
		coin = coin + z
	elif rem % 2 == 0 or rem == 1:
		z = int(s / n + 1)
		coin = coin + z
	else:
		z = int(s / n + 2)
		coin = coin + z
	print(coin)


for _ in range(int(input())):
	(s, n) = map(int, input().split())
	if s <= n:
		if s % 2 == 0 or s == 1:
			print(1)
		else:
			print(2)
	else:
		if n == 1:
			print(s)
			continue
		if n % 2 == 1:
			n -= 1
		if s % n == 0:
			print(s // n)
		else:
			p = s % n
			if p % 2 == 1 and p != 1:
				print(s // n + 2)
			else:
				print(s // n + 1)


for _ in range(int(input())):
	(s, n) = map(int, input().split())
	if n % 2 == 0:
		c = n
	else:
		c = n - 1
	x = s // c
	y = s % c
	if y == 0:
		print(x)
	elif y == 1:
		print(x + 1)
	elif y % 2 == 0:
		print(x + 1)
	else:
		print(x + 2)


for i in range(int(input())):
	(s, n) = [int(num) for num in input().split()]
	dum = 0
	if s == n:
		print(1)
	elif s == 1:
		print(1)
	elif s < n:
		if s % 2 == 0:
			print(1)
		elif s % 2 != 0:
			print(2)
	elif n < s:
		if s % n == 0:
			print(s // n)
		elif s % n % 2 == 0 or s % n == 1:
			print(s // n + 1)
		else:
			print(s // n + 2)


t = int(input())
for i in range(t):
	(s, n) = map(int, input().split())
	c = s // n
	r = s % n
	if r == 0:
		print(c)
	elif r % 2 != 0 and r != 1:
		print(c + 2)
	else:
		print(c + 1)


t = int(input())
for i in range(t):
	s_n = input().split(' ')
	(s, n, n_coins) = (int(s_n[0]), int(s_n[1]), 0)
	if s > n:
		if s % n == 0:
			print(s // n)
		elif s % n % 2 == 0:
			print(s // n + 1)
		elif s % n == 1:
			print(s // n + 1)
		elif s % n % 2 == 1:
			print(s // n + 2)
	elif s == n:
		print(1)
	elif s % 2 == 0:
		print(1)
	elif s == 1:
		print(1)
	else:
		print(2)


f = int(input())
pl = []
for mm in range(0, f):
	awe = str(input())
	xdf = awe.split(' ')
	ii = []
	for nbv in xdf:
		ii.append(int(nbv))
	pl.append(ii)
for xzx in pl:
	upo = xzx[0]
	rpo = xzx[1]
	if upo < rpo:
		if upo % 2 == 0:
			print(1)
		elif upo == 1:
			print(1)
		else:
			print(2)
	elif upo == rpo:
		print(1)
	elif upo % rpo == 0:
		print(upo // rpo)
	else:
		jkl = upo // rpo
		hnr = upo % rpo
		if hnr == 1:
			print(jkl + 1)
		elif hnr % 2 == 0:
			print(jkl + 1)
		else:
			print(jkl + 2)


def main():
	for _ in range(int(input())):
		count = 0
		(b, n) = map(int, input().split())
		while b > 0:
			count = count + b // n
			b = b % n
			if b >= 2:
				if b % 2 == 0:
					n = b
				else:
					n = b - 1
			else:
				n = 1
		print(count)
main()


for _ in range(int(input())):
	(s, n) = map(int, input().split())
	c = 0
	if s <= n or s == 1:
		if s % 2 == 0 or s == 1:
			print(1)
		else:
			print(2)
	else:
		while n > 0:
			if n > s:
				n = s if s % 2 == 0 else s - 1
			else:
				c += s // n
				s = s % n
				n = n - 2
		print(c + s)


for i in range(int(input())):
	(s, n) = map(int, input().split())
	sum1 = 0
	if s < n:
		if s == 1:
			print(1)
		elif s % 2 == 0:
			print(1)
		else:
			print(2)
	elif n % 2 == 0:
		sum1 += s // n
		rem = s % n
		if rem == 0:
			print(sum1)
		elif rem % 2 == 0:
			print(sum1 + 1)
		elif rem == 1:
			print(sum1 + 1)
		else:
			print(sum1 + 2)
	else:
		n = n - 1
		sum1 += s // n
		rem = s % n
		if rem == 0:
			print(sum1)
		elif rem % 2 == 0:
			print(sum1 + 1)
		elif rem == 1:
			print(sum1 + 1)
		else:
			print(sum1 + 2)


T = int(input())
for i in range(T):
	(S, N) = map(int, input().split())
	ans = S // N
	if S % N % 2 and S % N > 1:
		ans += 2
	elif S % N > 0:
		ans += 1
	print(ans)


for x in range(int(input())):
	(b, a) = list(map(int, input().split()))
	c = 0
	if b >= a:
		d = b // a
		c += d
		r = b - d * a
		if r % 2 == 0 and r != 0:
			c += 1
		elif r % 2 != 0 and r != 1:
			c += 2
		elif r == 1:
			c += 1
	elif b < a:
		if b == 1:
			c += 1
		elif b % 2 == 0:
			c += 1
		else:
			c += 2
	print(c)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	t = 0
	if n % 2 != 0:
		n -= 1
		t += 1
	t += n // k
	if n % k != 0:
		t += 1
	print(t)


for _ in range(int(input())):
	(s, n) = map(int, input().strip().split())
	c = s // n
	s = s % n
	if s % 2 and s > 1:
		c += 2
	elif s > 0:
		c += 1
	print(c)


t = int(input())
for i in range(t):
	(s, n) = map(int, input().split())
	ans = 0
	while True:
		ans += s // n
		s = s % n
		if s == 0:
			break
		elif s == 1 or s % 2 == 0:
			ans += 1
			break
		else:
			n = s - 1
	print(int(ans))


try:
	for _ in range(int(input())):
		(s, n) = map(int, input().split())
		if s > n:
			c = s // n
			r = s % n
			if r == 0:
				print(c)
			elif r == 1:
				print(c + 1)
			elif r % 2 == 0:
				print(c + 1)
			else:
				print(c + 2)
		elif s % 2 == 0:
			print('1')
		elif s == 1:
			print('1')
		else:
			print('2')
except:
	pass


for _ in range(int(input())):
	(S, N) = (int(i) for i in input().strip().split())
	coinCount = 0
	if S % 2 == 1:
		S -= 1
		coinCount += 1
	coinCount += S // N
	if S % N != 0:
		coinCount += 1
	print(coinCount)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	c = 0
	c += n // m
	p = n % m
	if p >= 1:
		if p % 2 == 0 or p == 1:
			c += 1
			print(c)
		else:
			c += 2
			print(c)
	else:
		print(c)


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


t = int(input())
while t > 0:
	(s, n) = map(int, input().split())
	c = 0
	if s <= n:
		if s % 2 == 0:
			print('1')
		elif s == 1:
			print('1')
		else:
			print('2')
	else:
		if s % 2 != 0:
			c += 1
			s -= 1
		c += s // n
		if s % n == 0:
			print(c)
		else:
			print(c + 1)
	t -= 1


t = int(input())
for _ in range(t):
	(s, n) = [int(x) for x in input().split()]
	ans = 0
	if s == n:
		ans = 1
	elif s > n:
		ans += s // n
		s = s % n
		if s % 2 == 1:
			ans += 1
		if s != 1 and s != 0:
			ans += 1
	else:
		if s % 2 == 1:
			ans += 1
		if s != 1 and s != 0:
			ans += 1
	print(ans)


for _ in range(int(input())):
	(s, n) = map(int, input().split())
	coins = int(s / n)
	if s % n % 2 == 1 and s % n != 1:
		print(coins + 2)
	elif s % n == 0:
		print(coins)
	else:
		print(coins + 1)


for t in range(int(input())):
	(s, n) = map(int, input().split())
	if s == 1:
		print(1)
	elif s == n:
		print(1)
	elif s < n and s % 2 == 1:
		print(2)
	elif s > n and s % n == 0:
		print(s // n)
	else:
		k = s // n
		if s % n % 2 == 0:
			print(k + 1)
		elif s % n == 1:
			print(k + 1)
		else:
			print(k + 2)


t = int(input())
for x in range(0, t):
	(s, n) = list(map(int, input().split()))
	coin = 0
	if s > n:
		rem = s % n
		coin += int(s / n)
		if rem % 2 == 0 and rem != 0:
			print(coin + 1)
		elif rem == 0:
			print(coin)
		elif rem == 1:
			print(coin + 1)
		elif rem % 2 >= 1:
			print(coin + 2)
	elif s <= n:
		if s % 2 == 0:
			print(coin + 1)
		elif s == 1:
			print(coin + 1)
		elif s % 2 >= 1 and s != 1:
			print(coin + 2)


for x in range(int(input())):
	(S, N) = list(map(int, input().split()))
	total = 0
	if S > N:
		a = S // N
		total += a
		left = S - a * N
		if left % 2 == 0 and left != 0:
			total += 1
		elif left % 2 != 0 and left != 0 and (left != 1):
			total += 2
		elif left == 1:
			total += 1
	elif S == N:
		total += 1
	elif S < N:
		if S == 1:
			total += 1
		elif S % 2 == 0:
			total += 1
		elif S % 2 != 0:
			total += 2
	print(total)


t = int(input())
for _ in range(t):
	(s, n) = map(int, input().split())
	count = 0
	if s % 2 != 0:
		count = 1
		s = s - 1
	if s != 0:
		temp = int(s / n)
		count = count + temp
		s = s - n * temp
		if s < n and s != 0:
			count = count + 1
	print(count)


t = int(input())
for i in range(t):
	(s, n) = map(int, input().split())
	if n == 1:
		print(s)
	else:
		res = s // n
		rem = s % n
		if rem != 0:
			if rem % 2 == 0 or rem == 1:
				res = res + 1
			else:
				res = res + 2
		print(res)


t = int(input())
for _ in range(t):
	(s, n) = map(int, input().split())
	cnt = 0
	curr = n
	while s > 0 and curr != 0:
		cnt += s // curr
		s = s % curr
		curr = s // 2 * 2
	if s > 0:
		cnt += 1
	print(cnt)


import math
for i in range(int(input())):
	(s, n) = map(int, input().split())
	n_coins = s // n
	if s % n == 0:
		print(n_coins)
	else:
		rem = s % n
		if rem % 2 == 1 and rem != 1:
			print(n_coins + 2)
		else:
			print(n_coins + 1)


for t in range(int(input())):
	(s, n) = map(int, input().split())
	x = 0
	if s % 2 != 0:
		s -= 1
		x += 1
	x += s // n
	if s % n != 0:
		x += 1
	print(x)


for i in range(int(input())):
	(s, n) = map(int, input().split())
	x = s // n
	m = s - x * n
	if m > 1:
		x += 1
	if s % 2 != 0:
		x += 1
	print(x)


for i in range(int(input())):
	(s, n) = map(int, input().split())
	r3 = 0
	r1 = int(s / n)
	r2 = s % n
	if r2 != 0:
		if r2 % 2 == 0:
			r3 = 1
		elif r2 == 1:
			r3 = 1
		else:
			r3 = 2
	print(r1 + r3)


T = int(input())
for index in range(T):
	(s, n) = map(int, input().split())
	if s == n:
		print(1)
	elif s > n:
		c = 0
		c = c + s // n
		s = s % n
		if s > 1:
			if s % 2 == 0:
				c = c + 1
			else:
				c = c + 2
		elif s == 1:
			c = c + 1
		else:
			pass
		print(c)
	else:
		c = 0
		if s > 1:
			if s % 2 == 0:
				c = c + 1
			else:
				c = c + 2
		elif s == 1:
			c = c + 1
		else:
			pass
		print(c)


for _ in range(int(input())):
	(s, n) = list(map(int, input().split()))
	biggest = n // 2 * 2
	(coins, balance) = divmod(s, biggest)
	if balance == 0:
		print(coins)
	elif balance == 1 or balance % 2 == 0:
		print(coins + 1)
	else:
		print(coins + 2)


T = int(input())
for _ in range(T):
	(s, n) = map(int, input().split())
	ans = 0
	while s:
		ans += s // n
		s = s % n
		if s == 0:
			break
		elif s == 1 or s % 2 == 0:
			ans += 1
			break
		else:
			n = s - 1
	print(int(ans))


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


for _ in range(int(input())):
	(s, n) = map(int, input().split())
	left = s
	coins = 0
	while left > 0:
		largest = min(n, left)
		if largest > 2:
			largest -= largest % 2
		x = left // largest
		coins += x
		left -= x * largest
	print(coins)


for i in range(int(input())):
	(S, N) = map(int, input().split())
	count = 0
	if S == 1:
		print(1)
	elif S <= N:
		if S % 2 == 0:
			print(1)
		else:
			print(2)
	elif S % N == 0:
		print(S // N)
	elif S % N % 2 == 0:
		print(S // N + 1)
	elif S % N == 1:
		print(S // N + 1)
	else:
		print(S // N + 2)


for tc in range(int(input())):
	(s, n) = map(int, input().split())
	c = 0
	c = s // n
	rem = s % n
	add = 0
	if rem == 0:
		add = 0
	elif rem == 1:
		add = 1
	elif rem % 2 == 0:
		add = 1
	elif rem % 2 != 0:
		add = 2
	print(c + add)


a = int(input())
for i in range(a):
	(s, n) = map(int, input().split(' '))
	if n % 2 == 0:
		N = n
	else:
		N = n - 1
	coin = s // N
	rem = s % N
	if rem == 0:
		print(coin)
	elif rem == 1:
		print(coin + 1)
	elif rem % 2 == 0:
		print(coin + 1)
	else:
		print(coin + 2)


t = int(input())
for tc in range(t):
	(s, n) = map(int, input().split())
	a = s // n
	if s % 2 == 0:
		if s % n != 0:
			a += 1
	elif s % n == 1:
		a += 1
	else:
		a += 2
	print(a)


for T in range(int(input())):
	(s, n) = list(map(int, input().split()))
	coins = 0
	if s % 2 != 0:
		s -= 1
		coins += 1
	coins += s // n
	if s % n != 0:
		coins += 1
	print(coins)


t = int(input())
while t > 0:
	t -= 1
	(s, n) = map(int, input().split())
	if s == 1:
		print(1)
		continue
	res = 0
	i = 0
	res = res + s // n
	m = s % n
	if m == 0:
		print(res)
		continue
	if m % 2 == 0 or m == 1:
		res = res + 1
	else:
		res = res + 2
	print(res)


for tc in range(int(input())):
	(s, n) = map(int, input().split())
	if s % 2 == 0:
		tot = s // n
		if s % n != 0:
			tot += 1
	else:
		tot = s // n
		if s % n == 1:
			tot += 1
		else:
			tot += 2
	print(tot)


for I in range(int(input())):
	(a, b) = map(int, input().split())
	if a % b == 0:
		print(a // b)
	else:
		m = a % b
		if m % 2 == 0 or m == 1:
			k = a // b + 1
		else:
			k = a // b + 2
		print(k)


for t in range(int(input())):
	(S, N) = map(int, input().split())
	n = int(S / N)
	if S % N % 2 == 1 and S % N != 1:
		print(n + 1 + 1)
	elif S % N == 0:
		print(n)
	else:
		print(n + 1)


t = int(input())
for t in range(t):
	(s, n) = [int(i) for i in input().split()]
	m = int(s / n)
	k = s % n
	if s <= n and s % 2 == 0 or s == 1:
		print(1)
	elif k != 0 and k % 2 == 0 or k == 1:
		print(m + 1)
	elif k == 0:
		print(m)
	else:
		print(m + 2)


for _ in range(int(input())):
	(k, n) = map(int, input().split())
	m = int(k / n)
	j = int(k % n)
	if k == 1 or (k <= n and k % 2 == 0):
		print('1')
	elif j != 0 and j % 2 == 0 or j == 1:
		print(m + 1)
	elif j == 0:
		print(m)
	else:
		print(m + 2)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	if a % b == 0 and a // b >= 1:
		print(a // b)
	elif a % b != 0 and a // b >= 1:
		s = a % b
		if s % 2 == 0 or s == 1:
			print(a // b + 1)
		else:
			print(a // b + 2)
	elif a % b % 2 == 0 or a == 1:
		print(1)
	else:
		print(2)


def fun(s):
	if s % 2 == 0 or s == 1:
		return 1
	else:
		return 2
for test_cases in range(int(input())):
	(s, n) = map(int, input().split())
	ans = None
	if s <= n:
		ans = fun(s)
	else:
		ans = s // n
		if s % n != 0:
			ans += fun(s % n)
	print(ans)


for i in range(int(input())):
	(s, n) = map(int, input().split())
	if s % n == 0:
		print(s // n)
	else:
		r = s % n
		if r % 2 == 0 or r == 1:
			print(s // n + 1)
		else:
			print(s // n + 2)


for _ in range(int(input())):
	(s, n) = map(int, input().split())
	ans = s // n
	if s % n == 0:
		pass
	elif s % n == 1:
		ans += 1
	elif s % n & 1:
		ans += 2
	else:
		ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	(s, n) = map(int, input().split())
	if 1:
		ans = s // n
		rem = s % n
		if rem % 2 and rem > 1:
			ans += 2
		elif rem > 0:
			ans += 1
		print(ans)


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


t = int(input())
for ni in range(t):
	(s, n) = map(int, input().split())
	n_coins = s // n
	if s % n == 0:
		print(n_coins)
	else:
		rem = s % n
		if rem % 2 == 1 and rem != 1:
			print(n_coins + 2)
		else:
			print(n_coins + 1)


for _ in range(int(input())):
	(s, n) = list(map(int, input().split()))
	count = 0
	if s > n:
		rem = s % n
		count += s // n
		if rem % 2 == 0:
			if rem != 0:
				count += 1
		elif rem == 1:
			count += 1
		else:
			count += 2
	elif s < n:
		if s % 2 == 0:
			count += 1
		elif s == 1:
			count += 1
		else:
			count += 2
	else:
		count += 1
	print(count)


t = int(input())
for z in range(t):
	(s, n) = map(int, input().split())
	if s == 1:
		print('1')
		continue
	result = 0
	i = 0
	result = result + s // n
	mod = s % n
	if mod == 0:
		print(result)
		continue
	if mod % 2 == 0 or mod == 1:
		result = result + 1
	else:
		result = result + 2
	print(result)