Today is your birthday. You have decided to give away candies to your friends. 

You have N friends and M candies. Suppose the 1^{st} friend has L buckets, 2^{nd} has L+1 buckets, 3^{rd} has L+2 buckets, and so on — in general, the i^{th} friend has L + i - 1 buckets. 

You start distributing candies from the N^{th} friend and go towards the 1^{st} friend. 

For each friend, you put the maximum number of candies in each bucket such that all the buckets for that friend have an equal number of candies in them. Now, you take the remaining candies, move to the next friend, and repeat the above step. 

Find the number of candies which will remain with you after visiting all your friends.

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

- The first line of input will contain a single integer T, the number of test cases. Then the test cases follow.
- Each test case consists of a single line of input, containing three space-separated integers N, M, L — representing the number of friends, number of candies that you have, and the number of buckets with the 1^{st} friend respectively.

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

For each test case, output a single integer representing the total number of candies left with you after distributing candies to all your friends.

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

$1 ≤ T ≤ 10^{5}$
$0 ≤ N, M ≤ 10^{18}$
$1 ≤ L ≤ 10^{18}$

----- Sample Input 1 ------ 
4
2 8 2
3 9 2
3 10 2
4 100 10
----- Sample Output 1 ------ 
0
1
0
9
----- explanation 1 ------ 
Test case $1$: There are two friends. The $1^{st}$ friend has $2$ buckets and the $2^{nd}$ friend has $3$ buckets. You will give $6$ candies to $2^{nd}$ friend ($2$ in each bucket). Now you are left with $2$ candies, which you will give to the $1^{st}$ friend ($1$ in each bucket). You will be left with $0$ candies at the end.

Test case $2$: There are $3$ friends and $9$ candies. The $1^{st}$ friend has $2$ buckets, $2^{nd}$ friend has $3$ buckets, and $3^{rd}$ friend has $4$ buckets. You will give $8$ candies to the $3^{rd}$ friend ($2$ in each bucket). Now the $2^{nd}$ friend and $1^{st}$ friend will get $0$ candies. You will be left with $1$ candy at the end.

Test case $3$: There are $3$ friends and $10$ candies. You will give $8$ candies to the $3^{rd}$ friend ($2$ in each bucket). Next, the $2^{nd}$ friend will get $0$ candies. Finally, the $1^{st}$ friend will get $2$ candies ($1$ in each bucket). You will be left with $0$ candies at the end.

Difficulty: MEDIUM
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
for _ in range(int(input())):
	(n, m, l) = map(int, input().split())
	ans = m % (l + n - 1)
	if n == 0:
		print(m)
	elif ans < l:
		print(ans)
	else:
		print(0)


t = int(input())
while t:
	t -= 1
	(n, m, k) = map(int, input().split())
	if n == 0:
		print(m)
		continue
	v = k + n - 1
	m %= v
	if m >= k:
		m = 0
	print(m)


T = int(input())
while T != 0:
	(n, m, l) = tuple(map(int, input().split()))
	q = l + n - 1
	if n == 0:
		print(m)
	elif m % q >= l:
		print(0)
	else:
		print(m % q)
	T -= 1


def solve(n, m, l):
	curr = l + n - 1
	while n > 0 and m // curr != 0:
		m -= m // curr * curr
		curr -= 1
		n -= 1
	if l <= m <= curr:
		return 0
	return m
for _ in range(int(input())):
	(n, m, l) = list(map(int, input().split()))
	print(solve(n, m, l))


t = int(input())
for i in range(t):
	s = input().split()
	n = int(s[0])
	m = int(s[1])
	l = int(s[2])
	b = l + n - 1
	while b >= l:
		m = m % b
		b = m
	print(m)


t = int(input())
for _ in range(t):
	(n, m, l) = map(int, input().split())
	if n == 0:
		print(m)
		continue
	s = l + n - 1
	while m >= l:
		m %= s
		s = m
	print(m)


def binarySearch(l, r, x):
	ans = 0
	while l <= r:
		mid = l + (r - l) // 2
		if mid <= x:
			l = mid + 1
			ans = mid
		else:
			r = mid - 1
	return ans
t = int(input())
for _ in range(t):
	(n, m, l) = map(int, input().split())
	x = l + n - 1
	rem = m
	while x >= l and rem > 0:
		ans = binarySearch(l, x, rem)
		if ans == 0:
			break
		rem %= ans
		x = ans - 1
	print(rem)


t = int(input())
for tc in range(t):
	(n, m, l) = map(int, input().split())
	i = n - 1
	while i >= 0:
		m = m % (l + i)
		i = m - l
	print(m)


t = int(input())
for i in range(t):
	(n, m, l) = map(int, input().split())
	temp = l + n - 1
	while temp >= l:
		m = m % temp
		temp -= 1
		if temp >= m and m >= l:
			temp = m
		else:
			break
	print(m)


t = int(input())
for _ in range(t):
	(n, m, l) = map(int, input().split())
	i = n + l - 1
	while i >= l:
		m = m % i
		i = m
	print(m)


def sol():
	(n, m, l) = map(int, input().split())
	i = n - 1
	while i >= 0:
		m = m % (i + l)
		i = m - l
	print(m)
for _ in range(int(input())):
	sol()


T = int(input())
for _ in range(T):
	(N, M, L) = map(int, input().split())
	i = N - 1
	while i >= 0:
		M = M % (L + i)
		i = M - L
	print(M)


t = int(input())
for _ in range(t):
	(n, m, l) = list(map(int, input().split()))
	if n == 0:
		print(m)
	else:
		x = m % (n + l - 1)
		if x < l:
			print(x)
		else:
			print(0)


for k in range(int(input())):
	(n, c, s) = map(int, input().split())
	j = s + n - 1
	while j >= s:
		c = c % j
		j = c
	print(c)


a = int(input())
for x in range(a):
	(b, c, d) = map(int, input().split())
	n = d + (b - 1)
	l = b - 1
	while n >= d:
		c = c % n
		if c >= d:
			n = c
		else:
			break
	print(c)


T = int(input())
for _ in range(T):
	(N, M, L) = map(int, input().split())
	if N == 0:
		print(M)
	else:
		M = M % (N + L - 1)
		if M >= L:
			print(0)
		else:
			print(M)


for _ in range(int(input())):
	(n, m, l) = map(int, input().split())
	if n == 0:
		print(m)
		continue
	an = l + n - 1
	r = m % an
	if r >= l:
		print(0)
	else:
		print(r)


def candy():
	(N, M, L) = map(int, input().split(' '))
	i = N - 1
	while i >= 0:
		M = M % (L + i)
		i = M - L
	print(M)
for _ in range(int(input())):
	candy()


for _ in range(int(input())):
	(n, m, l) = map(int, input().split())
	if n == 0:
		print(m)
	else:
		val = m % (n + l - 1)
		print(val if val < l else 0)


t = int(input())
for i in range(t):
	(N, M, L) = map(int, input().split())
	if N == 0:
		print(M)
	else:
		x = N + L - 1
		d = M % x
		if d >= L:
			d = 0
		print(d)


ins = int(input())
for i in range(ins):
	lis = input().split(' ')
	(N, M, L) = (int(lis[0]), int(lis[1]), int(lis[2]))
	out = 0
	for i in range(N, 0, -1):
		M = M % (L + i - 1)
		if M < L:
			break
		if M >= L and M <= L + i - 2:
			M = 0
			break
	print(M)


for _ in range(int(input())):
	(n, choco, l) = [int(x) for x in input().split()]
	flag = 0
	for i in range(n - 1, -1, -1):
		buckets = l + i
		choco = choco % buckets
		if choco < l:
			break
		if choco >= l and choco <= buckets - 1:
			choco = 0
			break
	print(choco)


for i in range(int(input())):
	(n, m, l) = map(int, input().split(' '))
	for i in range(n - 1, -1, -1):
		x = l + i
		m = m % x
		if m < l:
			break
		elif m >= l and m <= x - 1:
			m = 0
			break
	print(m)


t = int(input())
for z in range(t):
	(N, M, L) = map(int, input().split())
	if N == 0:
		print(M)
	else:
		x = N + L - 1
		r = M % x
		if r >= L:
			r = 0
		print(r)


for _ in range(int(input())):
	(n, m, l) = (int(i) for i in input().split())
	if n == 0:
		print(m)
	else:
		s = l + n - 1
		ans = m % s
		if ans >= l:
			print(0)
		else:
			print(ans)


t = int(input())
while t:
	t -= 1
	k = 0
	(n, m, l) = map(int, input().strip().split())
	if n > 0:
		k = l + n - 1
		m %= k
		if m > l - 1 and m < k:
			m = 0
	print(m)


for t in range(int(input())):
	(n, m, l) = [int(x) for x in input().rstrip().split()]
	if n == 0:
		print(m)
	else:
		x = m % (l + n - 1)
		if x < l:
			print(x)
		else:
			print(0)


T = int(input())
for _ in range(T):
	(N, M, L) = [int(x) for x in input().split()]
	if N == 0:
		print(M)
	else:
		remainder = M % (N + L - 1)
		if remainder < L:
			print(remainder)
		else:
			print(0)


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


def a(m, l, n):
	if m >= l + n - 1:
		return m % (l + n - 1)
	elif m < l:
		return m
	elif m == l:
		return 0
	elif m > l and m < l + n - 1:
		return 0
t = int(input())
while t:
	(n, m, l) = input().split()
	n = int(n)
	l = int(l)
	m = int(m)
	if n == 0:
		print(m)
	else:
		while m >= l:
			m = a(m, l, n)
		print(m)
	t -= 1


for i in range(int(input())):
	(n, m, l) = list(map(int, input().split()))
	if not n:
		print(m)
		continue
	m %= l + n - 1
	if m >= l:
		print(0)
	else:
		print(m)


def inp():
	return int(input())

def mp():
	return map(int, input().split())

def lst():
	return list(map(int, input().split()))
T = int(input())
for _ in range(T):
	(n, m, l) = mp()
	if n == 0:
		print(m)
	else:
		m = m % (l + n - 1)
		if m >= l:
			print(0)
		else:
			print(m)


for _ in range(int(input())):
	(n, m, l) = [int(i) for i in input().split()]
	buckets = l + n - 1
	while buckets >= l and m >= buckets:
		m %= buckets
		buckets -= 1
	if m >= l and m <= buckets:
		print(0)
	else:
		print(m)


def dis(n, m, l):
	i = n - 1
	while i >= 0:
		m = m % (l + i)
		i = m - l
	print(m)
try:
	for _ in range(int(input())):
		(n, m, l) = map(int, input().split())
		dis(n, m, l)
except:
	pass


t = int(input())
while t:
	t -= 1
	(n, m, l) = list(map(int, input().split()))
	x = l + n - 1
	rem = m % x
	res = rem
	if n == 0:
		print(m)
		continue
	if rem >= l:
		res = 0
	print(res)


t = int(input())
while t:
	t -= 1
	(n, m, l) = list(map(int, input().split()))
	i = l + n - 1
	while i >= l:
		m = m % i
		if i >= m:
			i = m
		else:
			i -= 1
	print(m)


T = int(input())
for i in range(T):
	(N, M, L) = map(int, input().split())
	n = L + N - 1
	ans = M
	while n >= L:
		ans = ans % n
		if n >= ans:
			n = ans
		else:
			n -= 1
	print(ans)


for _ in range(int(input())):
	(n, m, l) = list(map(int, input().split()))
	if n == 0:
		print(m)
		continue
	x = l + n - 1
	rem = m % x
	res = rem
	if rem >= l:
		res = 0
	print(res)


t = int(input())
for _ in range(t):
	(n, c, l) = map(int, input().split())
	if n == 0:
		print(c)
		continue
	c %= l + n - 1
	if c >= l and c < l + n - 1:
		print(0)
	else:
		print(c)


t = int(input())
for _ in range(t):
	(n, c, l) = map(int, input().split())
	i = n - 1
	while i >= 0:
		c = c % (l + i)
		i = c - l
	print(c)


t = int(input())
while t:
	(n, m, l) = map(int, input().split())
	i = n - 1
	while i >= 0:
		m = m % (l + i)
		i = m - l
	print(m)
	t -= 1


t = int(input())
while t:
	t -= 1
	(n, m, l) = map(int, input().split())
	if m == 0 or l == 1:
		print(0)
		continue
	if n == 0:
		print(m)
		continue
	modulo = m % (l + n - 1)
	if modulo >= l:
		print(0)
		continue
	print(modulo)


t = int(input())
for _ in range(t):
	(n, m, l) = map(int, input().split())
	pre = l + n - 1

	def solve(n, m, l):
		if n == 0:
			return m
		if m == 0:
			return 0
		if m % (l + n - 1) == 0 or (n > 1 and m % (l + n - 1) >= l):
			return 0
		return m % (l + n - 1)
	print(solve(n, m, l))


t = int(input())
for i in range(t):
	a = list(map(int, input().split()))
	n = a[0]
	m = a[1]
	l = a[2]
	p = l + (n - 1)
	if n == 0:
		print(m)
	else:
		m = m % p
		if m >= l:
			print(0)
		else:
			print(m)


t = int(input())
for _ in range(t):
	(n, c, m) = map(int, input().split())
	if n == 0:
		print(c)
		continue
	k = m + n - 1
	if c >= k:
		c %= k
	if c in range(m, m + n - 1):
		print(0)
	else:
		print(c)


for _ in range(int(input())):
	(n, m, l) = [int(a) for a in input().split()]
	z = l + n - 1
	if n == 0:
		print(m)
		continue
	while m > 0 and m >= l:
		val = m % z
		if val <= z - 1:
			z = val
		m = val
	print(m)


t = int(input())
while t > 0:
	(n, m, l) = map(int, input().split())
	if m == 0:
		print(0)
	elif n == 0:
		print(m)
	elif m % (l + n - 1) < l:
		print(m % (l + n - 1))
	else:
		print(0)
	t -= 1


for z in range(int(input())):
	(N, M, L) = map(int, input().split())
	tmp = N + L - 1
	if N == 0:
		print(M)
	elif M % tmp < L:
		print(M % tmp)
	else:
		print(0)


for tc in range(int(input())):
	(N, M, L) = map(int, input().split())
	i = N - 1
	while i >= 0:
		M = M % (L + i)
		i = M - L
	print(M)


for i in range(int(input())):
	(f, c, b) = map(int, input().split())
	lastb = min(b + f - 1, c)
	while c >= b and lastb >= b:
		give = lastb * (c // lastb)
		c -= give
		lastb = min(lastb - 1, c)
	print(c)


for _ in range(int(input())):
	(n, m, l) = map(int, input().split())
	buckets_n = n + l - 1
	if n == 0:
		print(m)
	elif m < l:
		print(m)
	elif m <= buckets_n:
		print(0)
	else:
		rem = m % buckets_n
		if rem == 0 or rem >= l:
			print(0)
		else:
			print(rem)


for i in range(int(input())):
	(n_friend, n_candies, min_bucket) = map(int, input().split())
	if n_friend == 0 or n_candies == 0:
		print(n_candies)
	else:
		n_candies %= n_friend + min_bucket - 1
		if n_candies >= min_bucket:
			print(0)
		elif n_candies < min_bucket:
			print(n_candies)


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(how_much_noob_I_am):
		(n, m, l) = sep()
		if n == 0:
			print(m)
			continue
		start = l
		end = n + l - 1
		rem = m % end
		if rem >= start:
			print(0)
		else:
			print(rem)
main()


for _ in range(int(input())):
	(n, m, l) = map(int, input().split())
	low = l
	high = l + n - 1
	while low <= high:
		if m < high:
			high = m
		else:
			m = m % high
			high = m
	print(m)


t = int(input())
for _ in range(0, t):
	inputs = [int(num) for num in input().split()]
	n = inputs[0]
	m = inputs[1]
	l = inputs[2]
	start = l + n - 1
	if start > m:
		start = m
	if m > 0 and n > 0:
		i = start
		while i >= l:
			if m >= i and i != 0:
				m = m % i
				i = m
			else:
				break
		print(m)
	else:
		print(m)


t = int(input())
while t:
	(n, m, l) = [int(i) for i in input().split()]
	flag = 0
	while n > 0:
		m = m % (l + n - 1)
		if m == 0:
			print(m)
			flag = 1
			break
		elif m < l:
			print(m)
			flag = 1
			break
		n = m - l + 1
	if flag == 0:
		print(m)
	t -= 1


no_of_test_cases = int(input())

def main():
	for i in range(no_of_test_cases):
		(n, m, l) = input().split()
		(n, m, l) = (int(n), int(m), int(l))
		r = print_result(n, m, l)
		print(r)

def print_result(n, m, l):
	if n == 0:
		return m
	candies = m
	low = l
	high = l + n - 1
	while True:
		if candies > high:
			candies = candies % high
			continue
		elif low <= candies <= high:
			return 0
		else:
			return candies
main()


t = int(input())
for i in range(t):
	(n, m, l) = map(int, input().split())
	a = l + n - 1
	k = m % a
	if n == 0:
		print(m)
	elif k < l:
		print(k)
	else:
		print('0')


T = int(input())
while T:
	(F, C, B) = list(map(int, input().split()))
	i = F - 1
	while i >= 0:
		C = C % (B + i)
		i = C - B
	print(C)
	T -= 1


import math
t = int(input())
while t:
	t -= 1
	(x, y, l) = map(int, input().split())
	if x == 0 or y == 0:
		print(y)
	elif y % (x + l - 1) >= l:
		print(0)
	else:
		print(y % (x + l - 1))


for _ in range(int(input())):
	(N, M, L) = map(int, input().split())
	x = L + N - 1
	r = M % x
	if N == 0:
		print(M)
	elif r < L:
		print(r)
	else:
		print(0)


def solve(n, m, l):
	candies = m
	i = n - 1
	while i >= 0 and candies > 0:
		left = candies % (i + l)
		candies = left
		i = left - l
	return candies

def main():
	for _ in range(int(input())):
		(n, m, l) = map(int, input().split())
		res = solve(n, m, l)
		print(res)
main()