Chef is baking delicious cookies today! Since Chef is super hungry, he wants to eat at least $N$ cookies.
Since Chef is a messy eater, he drops a lot of crumbs. Crumbs of $B$ cookies can be put together to make a new cookie! 
Given $N$ and $B$, help Chef find out the minimum number of cookies he must initially bake, $A$, to satisfy his hunger.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of  two space separated integers $N, B$. 

-----Output:-----
For each test case, print a single integer $A$, the minimum number of cookies Chef must bake initially.

-----Constraints-----
- $1 \leq T \leq 1000$
- $1 \leq N \leq 1000000000$
- $2 \leq B \leq 1000000000$

-----Sample Input 1:-----
1
3 2

-----Sample Output 1:-----
2

-----Sample Input 2:-----
1
11 2

-----Sample Output 2:-----
6

-----Explanation 2:-----
Chef initially make 6 cookies. From the crumbs, Chef makes 3 new cookies with no crumbs left over. From the crumbs of the new cookies, Chef makes 1 new cookie and have crumbs left from one cookie. From the new cookie, Chef gets more crumbs. He adds the crumbs and gets one last cookie. After eating that, there are not enough crumbs left to make a new cookie. So a total of 11 cookies are consumed!

Difficulty: HARD
Tags: Sorting

Mathematics

Complete search
Skill types: Sorting

Complete search

Starter code:

Solutions:
def f():
	t = int(input())
	while t > 0:
		t -= 1
		(n, b) = map(int, input().split())
		if b >= n:
			print(n)
		elif n % b == 0:
			ans = (n // b - 1) * (b - 1) + b
			print(ans)
		else:
			ans = ((n - 1) // b - 1) * (b - 1) + b + (n - 1) % b
			print(ans)
f()


def check(n, m):
	ct = 0
	if n >= m:
		ct = int(n / m)
		ct += check(int(n / m) + int(n % m), m)
	return ct

def bsearch(n, m):
	lo = 1
	hi = n
	while lo < hi:
		mid = int((lo + hi) / 2)
		val = mid + check(mid, m)
		if val >= n:
			hi = mid
		else:
			lo = mid + 1
	return lo
t = int(input())
while t > 0:
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	val = bsearch(n, m)
	print(val)
	t -= 1


def fun(n, b):
	if n <= b:
		return n
	n = n - 1
	a = n // b
	d = b - 1
	r = n % b
	return 1 + a * d + r
t = int(input())
l = []
for i in range(t):
	(n, b) = tuple(map(int, input().split()))
	l.append(fun(n, b))
for i in l:
	print(i)


for _ in range(int(input())):
	(N, B) = map(int, input().split())
	ans = N - (N - 1) // B
	print(ans)


for _ in range(int(input())):
	(n, b) = [int(x) for x in input().split()]
	print(n - int((n - 1) / b))


def finder(k):
	eaten = 0
	crumbs = 0
	while k > 0:
		eaten += k
		crumbs += k
		k = crumbs // b
		crumbs %= b
	return eaten

def search(N):
	lo = 1
	hi = N
	while lo < hi:
		mid = (lo + hi) // 2
		total = finder(mid)
		if total < n:
			lo = mid + 1
		else:
			hi = mid
	print(hi)
for _ in range(int(input())):
	(n, b) = map(int, input().split())
	search(n)


for i in range(int(input())):
	(n, b) = list(map(int, input().split()))
	print(1 + n * (b - 1) // b)


t = int(input())
for _ in range(t):
	(n, b) = map(int, input().split())
	low = 0
	high = n
	while low < high:
		mid = (low + high) // 2
		cook = mid
		left = mid
		while True:
			book = left // b
			if book == 0:
				break
			left = book + left % b
			cook += book
		if high - low < 3:
			for i in range(low, high + 1):
				cook = i
				left = i
				while True:
					book = left // b
					if book == 0:
						break
					left = book + left % b
					cook += book
				ans = i
				if cook >= n:
					break
			break
		if cook > n:
			ans = mid
			high = mid
		elif cook < n:
			low = mid
		if cook == n:
			ans = mid
			high = mid
	print(ans)


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


import math
t = int(input())
while t > 0:
	(n, b) = map(int, input().split())
	tobemade = math.ceil((n * (b - 1) + 1) / b)
	print(tobemade)
	t -= 1


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


t = int(input())
for j in range(t):
	(a, b) = list(map(int, input().split()))
	L = 1
	R = a
	while R - L > 1:
		mid = (L + R) // 2
		cookies = mid
		crumbles = 0
		hours = mid
		while cookies > b - 1:
			crumbles = cookies % b
			hours += cookies // b
			cookies = cookies // b + crumbles
		if hours < a:
			L = mid + 1
		else:
			R = mid
	cookies = L
	crumbles = 0
	hours = L
	while cookies > b - 1:
		crumbles = cookies % b
		hours += cookies // b
		cookies = cookies // b + crumbles
	if hours < a:
		print(R)
	else:
		print(L)


def count(mid, b):
	ans = mid
	crumb = mid
	while crumb >= b:
		ans += crumb // b
		crumb = crumb // b + crumb % b
	return ans
for _ in range(int(input())):
	(n, b) = map(int, input().split())
	low = 1
	high = 10 ** 11
	while low <= high:
		mid = (low + high) // 2
		if count(mid, b) >= n:
			high = mid - 1
			ans = mid
		else:
			low = mid + 1
	print(ans)


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


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


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


t = int(input())
for _ in range(t):
	(n, b) = map(int, input().split())
	low = 1
	high = n
	if b == 1:
		print(1)
		continue
	while low < high and abs(high - low) > 4:
		mid = (low + high) // 2
		a = mid // b
		aa = mid % b
		d = mid
		while a:
			d += a
			tt = a + aa
			a = tt // b
			aa = tt % b
		if d >= n:
			high = mid
		if d < n:
			low = mid + 1
	for mid in range(low, high + 1):
		a = mid // b
		aa = mid % b
		d = mid
		while d < n and a:
			d += a
			tt = a + aa
			a = tt // b
			aa = tt % b
		if d >= n:
			tt = mid
			break
	print(tt)


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


test = int(input())
while test != 0:
	test = test - 1
	(n, b) = map(int, input().split())
	pp = n // b
	ans = n - pp
	if n % b == 0:
		ans += 1
	print(ans)


t = int(input())
i = 0
while t > i:
	(n, b) = map(int, input().split())
	ans = n - n // b
	if b == 1:
		print(1)
	elif not n % b:
		print(ans + 1)
	else:
		print(ans)
	i += 1


for i in range(int(input())):
	(n, b) = [int(x) for x in input().split()]
	ans = n - n // b
	if n % b == 0:
		ans += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	p = n
	sum = 0
	while n // (k + 1) != 0:
		sum += n // (k + 1)
		n -= k * (n // (k + 1))
	print(p - sum)


t = int(input())
while t:
	(n, b) = list(map(int, input().split()))
	ans = n - n // b
	if b == 1:
		print(1)
	elif n % b:
		print(ans)
	else:
		print(ans + 1)
	t -= 1


import math
for _ in range(int(input())):
	(N, B) = [int(x) for x in input().split()]
	print(math.ceil(N - N // B + (N % B == 0)))


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


def resck(a, c):
	cr = a
	net = a
	while cr >= c:
		new = cr // c
		net += new
		cr -= new * (c - 1)
	return net
for _ in range(int(input())):
	(n, b) = map(int, input().split())
	lo = 0
	hi = n
	while hi - lo > 1:
		md = (lo + hi) // 2
		if resck(md, b) < n:
			lo = md
		else:
			hi = md
	print(hi)


from math import ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print(n - (n - 1) // k)


t = int(input())
while t > 0:
	t -= 1
	(n, b) = [int(i) for i in input().split()]
	if int(n % b) == 0:
		print(n - int(n / b) + 1)
	else:
		print(n - int(n / b))


def cookies(N, B):
	ans = N
	crumbs = N
	while crumbs >= B:
		ans += crumbs // B
		crumbs = crumbs // B + crumbs % B
	return ans

def b_search(N, B):
	low = 1
	high = N
	ans = N
	while low < high:
		mid = low + (high - low) // 2
		qty = cookies(mid, B)
		if qty >= N:
			high = mid
			ans = mid
		else:
			low = mid + 1
	return ans
T = int(input())
for t in range(T):
	[N, B] = [int(i) for i in input().split()]
	print(b_search(N, B))


for _ in range(int(input())):
	(n, b) = input().split()
	(n, b) = (int(n), int(b))
	a = int(n / b)
	c = n - a
	if n % b == 0:
		c += 1
	print(c)