Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef is trying to invent the light bulb that can run at room temperature without electricity. So he has N gases numbered from 0 to N - 1 that he can use and he doesn't know which one of the N gases will work but we do know it.

Now Chef has worked on multiple search algorithms to optimize search. For this project, he uses a modulo-based search algorithm that he invented himself. So first he chooses an integer K and selects all indices i in increasing order such that i \bmod K = 0 and test the gases on such indices, then all indices i in increasing order such that i \bmod K = 1, and test the gases on such indices, and so on.

Given N, the index of the gas p that will work, and K, find after how much time will he be able to give Chefland a new invention assuming that testing 1 gas takes 1 day.

For example, consider N = 5, p = 2 and K = 3.
On the 1^{st} day, Chef tests gas numbered 0 because 0 \bmod 3 = 0.
On the 2^{nd} day, Chef tests gas numbered 3 because 3 \bmod 3 = 0.
On the 3^{rd} day, Chef tests gas numbered 1 because 1 \bmod 3 = 1.
On the 4^{th} day, Chef tests gas numbered 4 because 4 \bmod 3 = 1.
On the 5^{th} day, Chef tests gas numbered 2 because 2 \bmod 3 = 2.

So after 5 days, Chef will be able to give Chefland a new invention

------ Input Format ------ 

- 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 three space-separated integers N, p, and K.

------ Output Format ------ 

For each test case, print a single line containing one integer — after how much time Chef will be able to give Chefland a new invention assuming that testing 1 gas takes 1 day.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N, K ≤ 10^{9}$
$0 ≤ p < N$

------ subtasks ------ 

Subtask #1 (100 points): Original constraints

----- Sample Input 1 ------ 
4
10 5 5
10 6 5
10 4 5
10 8 5
----- Sample Output 1 ------ 
2
4
9
8
----- explanation 1 ------ 
Test case $1$: On the day $1$ Chef will test gas numbered $0$ and on the day $2$ Chef will test gas numbered $5$.

Test case $2$: On the day $1$ Chef will test gas numbered $0$, on the day $2$ Chef will test gas numbered $5$, on the day $3$ Chef will test gas numbered $1$, and on the day $4$ Chef will test gas numbered $6$.

Test case $3$: On the day $1$ Chef will test gas numbered $0$, on the day $2$ Chef will test gas numbered $5$, on the day $3$ Chef will test gas numbered $1$, on the day $4$ Chef will test gas numbered $6$, on the day $5$ Chef will test gas numbered $2$, on the day $6$ Chef will test gas numbered $7$, on the day $7$ Chef will test gas numbered $3$, on the day $8$ Chef will test gas numbered $8$, and on the day $9$ Chef will test gas numbered $4$.

Test case $4$: On the day $1$ Chef will test gas numbered $0$, on the day $2$ Chef will test gas numbered $5$, on the day $3$ Chef will test gas numbered $1$, on the day $4$ Chef will test gas numbered $6$, on the day $5$ Chef will test gas numbered $2$, on the day $6$ Chef will test gas numbered $7$, on the day $7$ Chef will test gas numbered $3$, and on the day $8$ Chef will test gas numbered $8$.

Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code:

Solutions:
import math
for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	if n % k == 0:
		x = p % k
		y = n // k
		print(x * y + math.ceil((p + 1) / k))
	elif n % k >= p % k + 1:
		x = p % k
		y = math.ceil(n / k)
		print(x * y + math.ceil((p + 1) / k))
	else:
		x = p % k
		y = math.ceil(n / k) - 1
		print(x * y + n % k + math.ceil((p + 1) / k))


t = int(input())
for i in range(t):
	(n, p, k) = list(map(int, input().split()))
	ans = n // k * (p % k) + p // k + min(n % k, p % k) + 1
	print(ans)


T = int(input())
for i in range(T):
	(N, p, K) = map(int, input().split())
	if (p + 1) % K == 0:
		a = K
	else:
		a = (p + 1) % K
	if a > N % K:
		print(N % K + (a - 1) * (N // K) + p // K + 1)
	else:
		print((a - 1) * (N // K + 1) + p // K + 1)


def main():
	for _ in range(int(input())):
		(n, p, k) = map(int, input().split())
		n = n - 1
		ans = p % k * (n // k) + (p // k + 1) + min(p % k, n % k + 1)
		print(ans)
main()


t = int(input())
for j in range(t):
	(n, p, k) = map(int, input().split())
	x = n // k
	res = min(n % k, p % k) + p % k * x + p // k + 1
	print(res)


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	c = p % k
	diff = n - n // k * k
	ans = 0
	base = n // k
	if c >= diff:
		ans += diff * (base + 1) + (c - diff) * base
	else:
		ans += c * (base + 1)
	ans += p // k + 1
	print(ans)


tc = int(input())
for _ in range(tc):
	(n, p, k) = map(int, input().split())
	m = p % k
	mod = 0
	if n % k != 0:
		num = (n - 1) // k + 1
	else:
		num = (n - 1) // k + 2
	if m >= n % k:
		mod = mod + num * (n % k)
		mod = mod + (num - 1) * (m - n % k)
	else:
		mod = mod + num * m
	x = (p - m) / k + 1
	mod += x
	print(int(mod))


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	x = n // k
	res = min(p % k, n % k) + p % k * x + p // k + 1
	print(res)


def soln(n, k, p):
	dest = p % k
	res = 0
	res = dest * (n // k)
	res += min(n % k, p % k)
	res += p // k + 1
	return res
for _ in range(int(input())):
	(n, p, k) = list(map(int, input().split()))
	print(soln(n, k, p))


try:
	for i in range(int(input())):
		(n, p, k) = input().split(' ')
		n = int(n)
		p = int(p)
		k = int(k)
		ans = 0
		a = p % k - 1
		b = (n - 1) // k * k
		b = n - 1 - b
		if a > b:
			ans += (b + 1) * ((n - 1) // k + 1) + (a - b) * ((n - 1) // k)
		else:
			ans += ((n - 1) // k + 1) * (a + 1)
		for i in range(a + 1, n, k):
			ans += 1
			if i == p:
				print(ans)
				break
except:
	pass


for t in range(int(input())):
	(n, p, k) = map(int, input().split())
	run = p % k
	longer_runs = min(n % k, run)
	shorter_runs = run - longer_runs
	ans = longer_runs * (n // k + 1) + shorter_runs * (n // k)
	ans += p // k + 1
	print(ans)


import math
t = int(input())
for _ in range(t):
	(N, p, K) = map(int, input().split())
	group = p % K
	group_size = int(math.ceil(N / K))
	large_group_count = N % K
	large_group_size = N // K + 1
	if group < large_group_count:
		count = group * large_group_size + (p - group) // K + 1
	else:
		count = large_group_count * large_group_size + (group - large_group_count) * (large_group_size - 1) + (p - group) // K + 1
	print(count)


t = int(input())
for _ in range(t):
	(n, p, k) = list(map(int, input().split()))
	r = p % k
	days = n // k * r
	x = n % k
	if x >= r:
		days += r
	else:
		days += x
	days += (p - r) // k + 1
	print(days)


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


T = int(input())
for _ in range(T):
	(N, p, K) = map(int, input().split())
	qr = p % K
	md = (N - 1) % K
	res = 0
	if qr > md:
		res = (md + 1) * (1 + (N - 1) // K) + (qr - md - 1) * ((N - 1) // K) + p // K + 1
	else:
		res = qr * (1 + (N - 1) // K) + p // K + 1
	print(res)


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	b = p // k + 1
	m = p % k
	a = (n - 1) // k + 1
	a1 = (n - 1) % k
	if m - 1 <= a1:
		print(a * m + b)
	else:
		print(a * (a1 + 1) + (a - 1) * (m - a1 - 1) + b)


for _ in range(int(input())):
	(n, k, p) = map(int, input().split())
	(t1, t2) = (0, 0)
	if n % p == 0:
		t1 = n // p
		ans = t1 * (k % p) + k // p + 1
		print(ans)
	else:
		t1 = n // p
		ans = t1 * (k % p) + k // p + 1
		t2 = n % p
		if k % p > t2:
			ans += t2
		else:
			ans += k % p
		print(ans)


def lösning(n, p, k):
	r = n % k
	i = p % k
	num = 1 + i * (n // k) + p // k
	if i < r:
		num += i
	else:
		num += r
	return num
T = int(input())
for i in range(T):
	(n, p, k) = map(int, input().split())
	print(lösning(n, p, k))


T = int(input())
for _ in range(T):
	(n, p, k) = map(int, input().split())
	r = n % k
	i = p % k
	num = 1 + i * (n // k) + p // k
	if i < r:
		num += i
	else:
		num += r
	print(num)


t = int(input())
for _ in range(t):
	(n, p, k) = list(map(int, input().split()))
	if n % k == 0:
		rows = k
		cols = n // k
		p_row = p % k + 1
		p_col = p // k + 1
		index = (p_row - 1) * cols + p_col
	else:
		rows = k
		cols = n // k
		p_row = p % k + 1
		p_col = p // k + 1
		boundary = rows * cols - 1
		extras = n - boundary - 1
		if p_row <= extras:
			index = (p_row - 1) * (cols + 1) + p_col
		else:
			index = extras * (cols + 1) + (p_row - extras - 1) * cols + p_col
	print(index)


t = int(input())
for _ in range(t):
	(n, p, k) = map(int, input().split())
	m = p % k
	ex = n % k
	reps = n // k
	days = m * reps + min(m, ex) + (p + k - m) // k
	print(days)


for i in range(int(input())):
	(n, p, k) = map(int, input().split())
	m = n // k
	rem = n % k
	p1 = p % k
	p = p // k
	if p1 >= rem:
		print(m * p1 + rem + p + 1)
	elif p1 == 0:
		print(p + 1)
	else:
		print(m * p1 + p1 + p + 1)


z = int(input())
for j in range(z):
	(n, p, k) = list(map(int, input().split()))
	jy = p % k
	n = n - 1
	cb = n // k * jy
	ans = cb + p // k + min(n % k, max(p % k - 1, 0)) + 1
	if p % k != 0:
		ans += 1
	print(ans)


try:
	for i in range(int(input())):
		(x, y, z) = input().split(' ')
		x = int(x)
		y = int(y)
		z = int(z)
		ans = 0
		a = y % z - 1
		b = (x - 1) // z * z
		b = x - 1 - b
		if a > b:
			ans += (b + 1) * ((x - 1) // z + 1) + (a - b) * ((x - 1) // z)
		else:
			ans += ((x - 1) // z + 1) * (a + 1)
		for i in range(a + 1, x, z):
			ans += 1
			if i == y:
				print(ans)
				break
except:
	pass


for _ in range(int(input())):
	(N, P, K) = map(int, input().split())
	print(N // K * (P % K) + P // K + 1 + min(N % K, P % K))


T = int(input())
for _ in range(T):
	(n, p, k) = map(int, input().split())
	ans = 0
	a = p % k - 1
	b = (n - 1) // k * k
	b = n - 1 - b
	if a > b:
		ans += (b + 1) * ((n - 1) // k + 1) + (a - b) * ((n - 1) // k)
	else:
		ans += ((n - 1) // k + 1) * (a + 1)
	for i in range(a + 1, n, k):
		ans += 1
		if i == p:
			print(ans)
			break


t = int(input())
for r in range(t):
	(n, p, k) = [int(x) for x in input().split()]
	r = n // k * (p % k) + p // k + 1 + min(n % k, p % k)
	print(r)


t = int(input())
for _ in range(t):
	(n, p, k) = list(map(int, input().split()))
	m = p % k
	n -= 1
	res = 0
	res += (n // k + 1) * m
	res += p // k + 1
	if m > n % k:
		res -= m - (n % k + 1)
	print(res)


testcases = int(input())
for eachcase in range(testcases):
	(indices, gas, integer) = map(int, input().split())
	nums = (indices - 1) // integer
	morenum = (indices - 1) % integer
	howmuch = nums + 1
	modofsol = gas % integer
	indexinthatmod = gas // integer + 1
	if modofsol <= morenum:
		print(modofsol * howmuch + indexinthatmod)
	else:
		print((morenum + 1) * howmuch + (modofsol - morenum - 1) * nums + indexinthatmod)


t = int(input())
for _ in range(t):
	(n, p, k) = map(int, input().split())
	ans = 0
	pmod = p % k
	nmod = n % k
	pdiv = p // k
	ndiv = n // k
	perfMod = ndiv + 1 if nmod != 0 else ndiv
	norm = nmod if nmod != 0 else k
	if pmod < norm:
		ans = (ndiv + 1 - (nmod == 0)) * pmod + (pdiv + 1)
	else:
		ans = (ndiv + 1 - (nmod == 0)) * norm + (pdiv + 1) + (pmod - norm) * ndiv
	print(ans)


a = int(input())
for i in range(a):
	(N, p, K) = map(int, input().split())
	b = (N - 1) // K + 1
	c = (N - 1) % K
	d = p // K
	e = p % K
	if e <= c:
		print(e * b + d + 1)
	else:
		print((c + 1) * b + (e - c - 1) * (b - 1) + d + 1)


t = int(input())
for _ in range(t):
	(n, p, k) = map(int, input().split())
	num = (n - 1) // k
	rem = n % k
	q = p // k + 1
	d = p % k
	if rem == 0:
		ans = d * (num + 1) + q
	elif rem > d:
		ans = d * (num + 1) + q
	else:
		ans = rem * (num + 1) + (d - rem) * num + q
	print(ans)


def solve(n, p, k):
	n -= 1
	if p % k <= n % k:
		return p // k + 1 + p % k * (n // k + 1)
	else:
		return p // k + 1 + (n % k + 1) * (n // k + 1) + (p % k - (n % k + 1)) * (n // k)
for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	print(solve(n, p, k))


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	n -= 1
	if p % k <= n % k:
		print(p // k + 1 + p % k * (n // k + 1))
	else:
		print(p // k + 1 + (n % k + 1) * (n // k + 1) + (p % k - (n % k + 1)) * (n // k))


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	mod = p % k
	a = n // k
	b = n % k
	days = a * mod + min(b, mod)
	days += p // k + 1
	print(days)


import math
t = int(input())
for _ in range(t):
	(n, p, k) = map(int, input().split())
	if (n - 1) % k == 0:
		a = (n - 1) // k + 1
	else:
		a = math.ceil((n - 1) / k)
	b = p % k
	if b <= (n - 1) % k:
		if b == 0:
			print(p // k + 1)
		else:
			print(a * b + math.ceil(p / k))
	else:
		c = b - (n - 1) % k
		print(a * ((n - 1) % k + 1) + (a - 1) * (c - 1) + math.ceil(p / k))


t = int(input())
while t > 0:
	t -= 1
	(n, p, k) = map(int, input().split())
	Nmod = n % k
	Pmod = p % k
	wrongMod = Pmod * (n // k) + 1
	if Nmod != 0:
		if Pmod != 0:
			wrongMod += min(Nmod, Pmod)
	days = wrongMod + (p - Pmod) // k
	print(days)


import sys
for x in range(int(input())):
	(n, p, k) = map(int, sys.stdin.readline().split())
	print(n // k * (p % k) + p // k + 1 + min(n % k, p % k))


def bulb(n, p, k):
	return p % k * (n // k) + min(p % k, n % k) + p // k + 1
for _ in range(int(input())):
	(n, p, k) = [int(x) for x in input().split()]
	result = bulb(n, p, k)
	print(result)


def main():
	for i in range(int(input())):
		(n, p, k) = input().split(' ')
		n = int(n)
		p = int(p)
		k = int(k)
		ans = 0
		a = p % k - 1
		b = (n - 1) // k * k
		b = n - 1 - b
		if a > b:
			ans += (b + 1) * ((n - 1) // k + 1) + (a - b) * ((n - 1) // k)
		else:
			ans += ((n - 1) // k + 1) * (a + 1)
		for i in range(a + 1, n, k):
			ans += 1
			if i == p:
				print(ans)
				break
main()


def inparr():
	tmparr = [int(i) for i in input().split()]
	return tmparr
for _ in range(int(input())):
	(N, p, K) = inparr()
	res = N // K * (p % K) + p // K + 1 + min(N % K, p % K)
	print(res)


import math
t = int(input())
for i in range(t):
	[N, p, K] = [int(i) for i in input().split()]
	info1 = p % K
	info2 = math.floor((N - 1) / K) + 1
	if info1 == 0:
		print(int((p - info1) // K) + 1)
	else:
		ans = info1 * info2
		ans += int((p - info1) // K) + 1
		info3 = (N - 1) % K
		if info1 >= info3 + 2:
			ans -= info1 - info3 - 1
		print(ans)


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	c = n % k
	d = p % k
	e = n // k
	f = -(-n // k)
	print(f * min(c, d) + e * max(0, d - c) + p // k + 1)


n = int(input())
for t in range(n):
	(N, p, K) = map(int, input().split())
	q = (N - 1) // K + 1
	if p % K <= (N - 1) % K:
		r = q * (p % K)
		r += p // K + 1
	else:
		r = q * ((N - 1) % K + 1)
		r += (q - 1) * (p % K - (N - 1) % K - 1)
		r += p // K + 1
	print(r)


t = int(input())
for tt in range(t):
	(n, p, k) = map(int, input().split())
	repeat_found = p % k + 1
	to_add = p // k + 1
	mult = n // k + 1
	max_mult = n % k + 1
	result = 0
	if repeat_found <= max_mult:
		result = mult * (repeat_found - 1) + to_add
	else:
		result = mult * max_mult + ((mult - 1) * (repeat_found - max_mult - 1) + (to_add - 1))
	print(result)


for _ in range(int(input())):
	(n, p, k) = map(int, input().split())
	b = p % k
	(b1, s2, s1) = (n % k, n // k, -(-n // k))
	print(s1 * min(b1, b) + s2 * max(0, b - b1) + p // k + 1)


for tastcas in range(int(input())):
	(n, p, k) = list(map(int, input().split()))
	n -= 1
	q = p % k - 1
	o = n // k
	m = n - o * k
	if q > m:
		ans = (m + 1) * (o + 1) + (q - m) * o
	else:
		ans = (o + 1) * (q + 1)
	for i in range(q + 1, n + 1, k):
		ans += 1
		if i == p:
			break
	print(ans)