Chef is trying to solve a problem having T test cases, where, for each test case he is given a single integer N.

Chef has an algorithm which takes exactly N^{2} iterations for a test case with value N.

The constraints of the problem are as follows:

1 ≤ T ≤ maxT
1 ≤ N ≤ maxN
Sum of N over all test cases does not exceed sumN.

Given the values maxT, maxN, and sumN, determine the maximum number of iterations Chef's algorithm can take for any valid input file satisfying all the constraints.

Formally speaking, find the maximum value of N_{1}^{2} + N_{2}^{2} + \dots + N_{T}^{2} for:
1 ≤ T ≤ maxT
1 ≤ N_{i} ≤ maxN
N_{1} + N_{2} + N_{3} +\dots +N_{T} ≤ sumN

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of single line consisting of three integers maxT, maxN, and sumN.

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

For each test case, output the the maximum number of iterations Chef's algorithm can take in any valid test file.

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

$1 ≤ T ≤ 1000$
$1 ≤ maxT ≤ maxN ≤ sumN ≤ 10^{4}$

----- Sample Input 1 ------ 
4
10 100 200
3 10 100
1000 1000 2200
100 100 100

----- Sample Output 1 ------ 
20000
300
2040000
10000

----- explanation 1 ------ 
Test Case $1$: Worst case for Chef's algorithm would be where $T=2$ and $N=100$ for both the test cases. In this case, Chef's algorithm will take $100^{2} + 100^{2} = 20000$ iterations.

Test Case $2$: Worst case for Chef's algorithm would be where $T=3$ and $N=10$ for all the $3$ test cases. In this case, Chef's algorithm will take $10^{2} + 10^{2} + 10^{2}= 300$ iterations.

Test Case $3$: Worst case for Chef's algorithm would be where $T=3$ and $N=1000, 1000,$ and $200$ for the three test cases respectively. In this case, Chef's algorithm will take $1000^{2} + 1000^{2} + 200^{2}= 2040000$ iterations.

Test Case $4$: Worst case for Chef's algorithm would be where $T=1$ and $N=100$. In this case Chef's algorithm will take $100^{2}= 10000$ iterations.

Difficulty: EASY
Tags: Mathematics

Starter code:

Solutions:
for _ in range(int(input())):
	(t, n, sn) = map(int, input().split())
	a = 0
	m = min(t, sn // n)
	if t > m:
		a = sn % n
	print(m * n * n + a * a)


import math
t = int(input())
for _ in range(t):
	(x, y, z) = map(int, input().split())
	s = x * y
	if s >= z:
		a = z // y
		k = y * a
		g = z - k
		result = a * y * y + g * g
		print(result)
	else:
		print(x * y * y)


t = int(input())
for _ in range(t):
	(m, p, t) = map(int, input().split())
	ans = 0
	sum = 0
	while m and t:
		n = p if t > p else t
		ans += pow(n, 2)
		m -= 1
		t -= n
	print(ans)


T = int(input())
for i in range(T):
	(maxT, maxN, sumN) = map(int, input().split(' '))
	t = int(sumN / maxN)
	if sumN % maxN != 0:
		t = t + 1
	if t > maxT:
		t = maxT
	s = 0
	for j in range(t):
		s = s + maxN ** 2
	if maxN * t > sumN:
		s = s - maxN ** 2
		n = sumN - maxN * (t - 1)
		s = s + n ** 2
	print(s)


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


import math
t = int(input())
for _ in range(t):
	(x, y, z) = map(int, input().split())
	d = x * y
	if d >= z:
		a = z // y
		k = y * a
		h = z - k
		result = a * y * y + h * h
		print(result)
	else:
		print(x * y * y)


t = int(input())
for i in range(t):
	(x, y, z) = map(int, input().split())
	c = x * y
	if c >= z:
		a = z // y
		k = y * a
		g = z - k
		result = a * y * y + g * g
		print(result)
	else:
		print(x * y * y)


for i in range(int(input())):
	(t, n, s) = map(int, input().split(' '))
	count = 0
	sum = 0
	while count != t:
		count += 1
		if s >= n:
			sum = sum + n * n
			s = s - n
		elif s < n:
			sum = sum + s * s
			break
	print(sum)


t = int(input())
while t > 0:
	(max_t, max_n, sum_n) = map(int, input().split())
	counter = 0
	l = []
	while sum_n > 0 and counter < max_t:
		if sum_n >= max_n:
			l.append(max_n)
		else:
			l.append(max_n - abs(sum_n - max_n))
		counter += 1
		sum_n -= max_n
	result = 0
	for i in range(counter):
		result += l[i] * l[i]
	print(result)
	t -= 1


for i in range(int(input())):
	(a, b, c) = map(int, input().split())
	if a * b <= c:
		q = 0
		while a > 0:
			q = q + b ** 2
			a -= 1
		print(q)
	else:
		q1 = 0
		if c % b == 0:
			w = c // b
			while w > 0:
				q1 = q1 + b ** 2
				w -= 1
			print(q1)
		else:
			q2 = 0
			w1 = c // b
			while w1 > 0:
				q2 = q2 + b ** 2
				w1 -= 1
			q2 = q2 + (c % b) ** 2
			print(q2)


for _ in range(int(input())):
	(x, y, z) = map(int, input().split())
	c = x * y
	if c >= z:
		j = z // y
		k = y * j
		l = z - k
		result = j * y * y + l * l
		print(result)
	else:
		print(x * y * y)


for i in range(int(input())):
	(maxT, maxN, sumN) = map(int, input().split())
	p = sumN % maxN
	a = sumN // maxN
	ans = 0
	if a <= maxT:
		ans += maxN ** 2 * a
		if a + 1 <= maxT:
			ans += p ** 2
		print(ans)
	else:
		print(maxN ** 2 * maxT)


for i in range(int(input())):
	(t, n, s) = map(int, input().split())
	d = 0
	while t > 0 and s > 0:
		if s >= n:
			d += n ** 2
		elif s > 0:
			d += s ** 2
		s = s - n
		t = t - 1
	print(d)


t = int(input())
for i in range(t):
	(a, b, c) = map(int, input().split())
	x = a * b
	if x >= c:
		y = c // b
		q = b * y
		z = c - q
		p = y * b * b + z * z
		print(p)
	else:
		print(a * b * b)


t = int(input())
for i in range(t):
	k = 0
	sum = 0
	(T, N, S) = map(int, input().split())
	while int(T) != 0 and int(S) - int(N) * k != 0 and (int(S) - int(N) * k >= int(N)):
		sum = sum + int(N) * int(N)
		T = T - 1
		k = k + 1
	if int(S) - int(N) * k < int(N) and int(S) - int(N) * k > 0 and (int(T) != 0):
		sum = sum + (int(S) - int(N) * k) ** 2
		print(sum)
	else:
		print(sum)


for _ in range(int(input())):
	(T_max, N_max, N_sum) = map(int, input().split())
	T = min(T_max, N_sum // N_max)
	last = 0 if T >= T_max else N_sum % N_max
	print(T * N_max ** 2 + last ** 2)


for _ in range(int(input())):
	(T_max, N_max, N_sum) = map(int, input().split())
	T = min(T_max, N_sum // N_max)
	last = N_sum % N_max
	print(T * N_max ** 2 + (T < T_max) * last ** 2)


for _ in range(int(input())):
	x = list(map(int, input().split()))
	(n, nt) = (0, [])
	for _ in range(x[0]):
		n += x[1]
		if n < x[2]:
			nt.append(x[1])
		else:
			nt.append(x[1] - n + x[2])
			break
	print(sum(map(lambda x: x ** 2, nt)))


t = int(input())
for i in range(t):
	(a, b, c) = map(int, input().split())
	total = 0
	while c > 0 and a > 0:
		if c >= b:
			total += b ** 2
			c -= b
		else:
			total += c ** 2
			c = 0
		a -= 1
	print(total)


import math
T = int(input())
for j in range(T):
	(X, Y, Z) = map(int, input().split())
	C = X * Y
	if C >= Z:
		A = Z // Y
		K = Y * A
		G = Z - K
		result = A * Y * Y + G * G
		print(result)
	else:
		print(X * Y * Y)


T = int(input())
for _ in range(T):
	(maxT, maxN, sumN) = map(int, input().split())
	ans = 0
	while maxT and sumN:
		n = maxN if sumN > maxN else sumN
		ans += n ** 2
		maxT -= 1
		sumN -= n
	print(ans)


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


t = int(input())
for _ in range(t):
	(maxT, maxN, sumN) = map(int, input().split())
	ans = 0
	sum = 0
	while maxT and sumN:
		n = maxN if sumN > maxN else sumN
		ans += pow(n, 2)
		maxT -= 1
		sumN -= n
	print(ans)


import math
T = int(input())
for I in range(T):
	(x, y, z) = map(int, input().split())
	c = x * y
	if c >= z:
		a = z // y
		k = y * a
		g = z - k
		rslt = a * y * y + g * g
		print(rslt)
	else:
		print(x * y * y)


def iterations(max_test, max_iter, iter_sum):
	total_iter = 0
	while max_test > 0 and iter_sum > 0:
		if iter_sum - max_iter >= 0:
			total_iter += max_iter * max_iter
		else:
			total_iter += iter_sum * iter_sum
		iter_sum -= max_iter
		max_test -= 1
	print(total_iter)
t = int(input())
for i in range(t):
	(T, N, S) = map(int, input().split())
	iterations(max_test=T, max_iter=N, iter_sum=S)


for i in range(int(input())):
	(maxT, maxN, sumN) = map(int, input().split())
	ans = 0
	while maxT and sumN:
		if sumN > maxN:
			n = maxN
		else:
			n = sumN
		ans += pow(n, 2)
		maxT -= 1
		sumN -= n
	print(ans)


for _ in range(int(input())):
	(t, n, s) = map(int, input().split())
	ans = 0
	while s > 0 and t > 0:
		if s - n >= 0:
			ans += n * n
		else:
			ans += s * s
		s -= n
		t -= 1
	print(ans)


import math
t = int(input())
for _ in range(t):
	(x, y, z) = map(int, input().split())
	c = x * y
	if c >= z:
		l = z // y
		k = y * l
		b = z - k
		result = l * y * y + b * b
		print(result)
	else:
		print(x * y * y)


def lis(a, b, c):
	if a * b <= c:
		s = 0
		for i in range(a):
			s = s + b ** 2
		print(s)
	else:
		k = c // b
		t = c % b
		l = 0
		for i in range(k):
			l = l + b ** 2
		print(l + t ** 2)
n = int(input())
for i in range(n):
	(a, b, c) = map(int, input().split())
	lis(a, b, c)


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	s = 0
	for i in range(1, a + 1):
		if b <= c:
			c -= b
			s += pow(b, 2)
		else:
			s += pow(c, 2)
			break
	print(s)


for _ in range(int(input())):
	(mT, mN, sN) = map(int, input().split())
	testList = []
	k = 0
	for i in range(1, mT + 1):
		if i * mN <= sN:
			testList.append(mN)
			k = i
	if mN * mT > sN and k * mN < sN:
		testList.append(sN - k * mN)
	maxVal = 0
	for i in testList:
		maxVal += i ** 2
	print(maxVal)


test_cases = int(input())
list_final = []
for t in range(test_cases):
	data = input()
	a = 0
	list_data = []
	for j in range(len(data)):
		if data[j] == ' ':
			list_data.append(data[a:j])
			a = j + 1
	list_data.append(data[a:])
	maxT = int(list_data[0])
	maxN = int(list_data[1])
	sumN = int(list_data[2])
	worstT = int(sumN / maxN) + 1
	if maxT < worstT:
		iter_final = maxT * maxN * maxN
	else:
		iter_final = (worstT - 1) * maxN * maxN + (sumN % maxN) ** 2
	list_final.append(iter_final)
for k in range(len(list_final)):
	print(list_final[k])


for i in range(int(input())):
	(maxt, maxn, sumn) = map(int, input().split())
	if sumn % maxn == 0:
		c = 0
	else:
		c = 1
	k = sumn // maxn
	if k + c <= maxt:
		print(k * maxn ** 2 + c * (sumn % maxn) ** 2)
	else:
		print(maxt * maxn ** 2)


for _ in range(int(input())):
	(x, y, z) = map(int, input().split())
	c = x * y
	if c >= z:
		a = z // y
		k = y * a
		g = z - k
		res = a * y * y + g * g
		print(res)
	else:
		print(x * y * y)


T = int(input())
for j in range(T):
	(maxT, maxN, sumN) = map(int, input().split())
	yes = 0
	count1 = 0
	maxN1 = 0
	for i in range(maxT):
		maxN1 += maxN
		if maxN1 > sumN - sumN % maxN:
			break
		count1 += maxN ** 2
		yes += 1
	if maxT > yes:
		count1 += (sumN % maxN) ** 2
	print(count1)


t = int(input())
for i in range(t):
	(mt, mn, sn) = map(int, input().split())
	q = sn // mn
	r = sn % mn
	if q >= mt:
		print(mt * mn * mn)
	else:
		print(q * mn * mn + r ** 2)


import math
q = int(input())
for i in range(q):
	(x, y, z) = map(int, input().split())
	c = x * y
	if c >= z:
		a = z // y
		k = y * a
		g = z - k
		result = a * y * y + g * g
		print(result)
	else:
		print(x * y * y)


t = int(input())
for _ in range(t):
	(maxT, maxN, sumN) = map(int, input().split())
	t_with_max_n = min(maxT, sumN // maxN)
	if t_with_max_n < maxT:
		rem_n = sumN % maxN
	else:
		rem_n = 0
	print(t_with_max_n * maxN ** 2 + rem_n ** 2)


for _ in range(int(input())):
	(mt, mn, sn) = map(int, input().split())
	if sn == mn:
		print(mn * mn)
	else:
		q = sn // mn
		r = sn % mn
		if mt <= q:
			print(mt * mn * mn)
		else:
			print(q * mn * mn + r * r)


n = int(input())
for i in range(n):
	sum = 0
	(a, b, c) = map(int, input().split())
	while a != 0 and c > 0:
		if c >= b:
			sum = sum + b ** 2
		else:
			sum = sum + c ** 2
		a = a - 1
		c = c - b
	print(sum)


t = int(input())
for i in range(t):
	(maxT, maxN, sumN) = map(int, input().split())
	print(min(sumN // maxN, maxT) * maxN * maxN + (sumN // maxN < maxT) * (sumN % maxN) * (sumN % maxN))


import math
s = int(input())
for i in range(s):
	(maxT, maxN, sumN) = map(int, input().split())
	n = math.ceil(sumN / maxN)
	if n < maxT:
		t = n
	else:
		t = maxT
	summ = 0
	ans = 0
	for j in range(t):
		if summ + maxN <= sumN:
			ans = ans + maxN * maxN
			summ = summ + maxN
		else:
			maxN = sumN - summ
			ans = ans + maxN * maxN
			break
	print(ans)


def solution():
	(maxT, maxN, sumN) = map(int, input().split())
	ans = 0
	while maxT and sumN:
		N = min(maxN, sumN)
		ans += N * N
		sumN -= N
		maxT -= 1
	print(ans)
T = int(input())
while T > 0:
	T -= 1
	solution()


import math
for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	if a * b <= c:
		print(a * b * b)
	else:
		x = math.floor(c / b)
		z = c - x * b
		print(x * b * b + z * z)


t = int(input())
for _ in range(t):
	(te, n, s) = map(int, input().split())
	ans = 0
	sum = 0
	while te and s:
		n = n if s > n else s
		ans += pow(n, 2)
		te -= 1
		s -= n
	print(ans)


t = int(input())
for i in range(t):
	(maxT, maxN, sumN) = input().split()
	m = int(maxN)
	s = 0
	f = 0
	n = int(maxT)
	a = 0
	for j in range(1, n + 1):
		s = s + m
		if s == int(sumN):
			f = j
			break
		elif s > int(sumN):
			s = s - m
			a = int(sumN) - s
			f = j - 1
			break
		elif j == n and s < int(sumN):
			f = n
	s1 = 0
	while f:
		s1 = s1 + m * m
		f = f - 1
	if a > 0:
		s1 = s1 + a * a
	print(s1)


t = int(input())
while t > 0:
	(maxT, maxN, SumN) = map(int, input().split())
	T = SumN // maxN
	r = SumN % maxN
	sum = 0
	if T < maxT:
		sum = T * maxN ** 2 + r ** 2
	else:
		sum = maxN ** 2 * maxT
	print(sum)
	t -= 1


n = int(input())
for i in range(0, n):
	(maxT, maxN, sumN) = tuple(map(int, input().split()))
	if maxT * maxN > sumN:
		k = int(sumN / maxN)
		rem = sumN % maxN
		print(maxN ** 2 * k + rem ** 2)
	else:
		print(int(maxN ** 2 * maxT))


for i in range(int(input())):
	(T, N, SN) = map(int, input().split())
	count = 0
	for i in range(T):
		if SN == 0:
			break
		if SN >= N:
			count += N ** 2
			SN -= N
		else:
			count += SN ** 2
			SN -= SN
	print(count)


def solution():
	my_string = input().split(' ')
	maxT = int(my_string[0])
	maxN = int(my_string[1])
	sumN = int(my_string[2])
	T = int(sumN / maxN)
	if T >= maxT:
		print(maxT * maxN ** 2)
	else:
		store = sumN % maxN
		print(T * maxN ** 2 + store ** 2)
test_cases = int(input())
for x in range(0, test_cases):
	solution()


for _ in range(int(input())):
	(t, n, s) = list(map(int, input().split()))
	if t <= s // n:
		print(t * (n * n))
	else:
		print(s // n * (n * n) + pow(s % n, 2))


t = int(input())
for i in range(t):
	(maxT, maxN, sumN) = map(int, input().split())
	maxIter = 0
	if maxT * maxN > sumN:
		while sumN != 0:
			if sumN > maxN:
				maxIter += pow(maxN, 2)
				sumN = sumN - maxN
			else:
				maxIter += pow(sumN, 2)
				sumN = 0
	else:
		for i in range(maxT):
			maxIter += pow(maxN, 2)
	print(maxIter)