Allison loves graph theory and just started learning about Minimum Spanning Trees(MST). She has three integers, $n$, $m$, and $\boldsymbol{\mathrm{~S~}}$, and uses them to construct a graph with the following properties:

The graph has $n$ nodes and $m$ undirected edges where each edge has a positive integer length.
No edge may directly connect a node to itself, and each pair of nodes can only be directly connected by at most one edge.
The graph is connected, meaning each node is reachable from any other node.
The value of the minimum spanning tree is $\boldsymbol{\mathrm{~S~}}$. Value of the MST is the sum of all the lengths of all edges of which are part of the tree.
The sum of the lengths of all edges is as small as possible.

For example, let's say $n=4$, $m=5$ and $s=4$. We need to construct a graph with $4$ nodes and $5$ edges. The value of minimum spanning tree must be $4$. The diagram belows shows a way to construct such a graph while keeping the lengths of all edges is as small as possible:

Here the sum of lengths of all edges is $7$.

Given $n$, $m$, and $\boldsymbol{\mathrm{~S~}}$ for $\mathrm{~g~}$ graphs satisfying the conditions above, find and print the minimum sum of the lengths of all the edges in each graph on a new line.

Note: It is guaranteed that, for all given combinations of $n$, $m$, and $\boldsymbol{\mathrm{~S~}}$, we can construct a valid graph.

Input Format

The first line contains an integer, $\mathrm{~g~}$, denoting the number of graphs. 

Each of the $\mathrm{~g~}$ subsequent lines contains three space-separated integers describing the respective values of $n$ (the number of nodes in the graph), $m$ (the number of edges in the graph), and $\boldsymbol{\mathrm{~S~}}$ (the value of the MST graph).

Constraints

For $20\%$ of the maximum score: 

$1$ $\leq$ $\mathrm{~g~}$ $\leq$ $100$
$2$ $\leq$ $n$ $\leq$ $10$
$1$ $\leq$ $m$ $\leq$ $50$
$1$ $\leq$ $\boldsymbol{\mathrm{~S~}}$ $\leq$ $\textbf{20}$

For $50\%$ of the maximum score: 

$1$ $\leq$ $\mathrm{~g~}$ $\leq$ $100$
$2$ $\leq$ $n$ $\leq$ $50$
$1$ $\leq$ $m$ $\leq$ $\textbf{2000}$
$1$ $\leq$ $\boldsymbol{\mathrm{~S~}}$ $\leq$ $\textbf{200}$

For $70\%$ of the maximum score: 

$1$ $\leq$ $\mathrm{~g~}$ $\leq$ $100$
$2$ $\leq$ $n$ $\leq$ $10^{5}$
$1$ $\leq$ $m$ $\leq$ $\mathbf{10}^{10}$
$1$ $\leq$ $\boldsymbol{\mathrm{~S~}}$ $\leq$ $10^{6}$

For $\textbf{100%}$ of the maximum score: 

$1$ $\leq$ $\mathrm{~g~}$ $\leq$ $\textbf{1000}$
$2$ $\leq$ $n$ $\leq$ $10^{8}$
$1$ $\leq$ $m$ $\leq$ $\mathbf{10}^{16}$
$1$ $\leq$ $\boldsymbol{\mathrm{~S~}}$ $\leq$ $\mathbf{10}^{10}$

Output Format

For each graph, print an integer on a new line denoting the minimum sum of the lengths of all edges in a graph satisfying the given conditions.

Sample Input
2
4 5 4
4 3 6

Sample Output
7
6

Explanation

Graph $1$:

The answer for this sample is already explained the problem statement.

Graph $2$:

We must construct a graph with $n=4$ nodes, $m=3$ edges, and an MST value of $s=6$. Recall that a connected graph with $n$ nodes and $n-1$ edges is already a tree, so the MST will contain all $m=3$ edges and the total length of all the edges of the graph will be equal to the value of the minimum spanning tree. So the answer is $\boldsymbol{6}$.

Source: hackerrank | Difficulty: HARD
Tags: Graph algorithms


Solutions:
import sys
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = input().strip().split(' ')
	(n, m, s) = [int(n), int(m), int(s)]
	if m <= (n - 1) * (n - 2) // 2 + 1:
		print(m + s - n + 1)
	else:
		s -= n - 1
		e = m - (n - 1) * (n - 2) // 2
		mnc = (s + n - 2) // (n - 1)
		ans = 1e+42
		s -= mnc
		for A in [0, s // (n - 2), s // (n - 2) - 1]:
			for B in [0, n - 3, (s - A * (n - 2)) % (n - 2)]:
				x = A * (n - 2) + B
				if 0 <= x <= s:
					ans = min(ans, (s - x + mnc) * e + (n - 1) * (n - 2) // 2 * A + B * (B - 1) // 2 + B * (n - B - 1))
		print(ans + m)


import sys
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = input().strip().split(' ')
	(n, m, s) = [int(n), int(m), int(s)]
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


import sys
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = input().strip().split(' ')
	(n, m, s) = [int(n), int(m), int(s)]
	if m <= n * (n - 1) // 2 - (n - 2):
		print(s - (n - 1) + m)
	else:
		n -= 2
		k = m - (n + 1) * n // 2
		s -= n
		ans = (n + 1) * n // 2 + k * s
		le = 1
		if n * (n + 1) // 2 <= k * n and s >= n:
			z = (s - le) // (n + 1)
			while le + z <= s - z * n:
				z += 1
			while le + z > s - z * n and z > 0:
				z -= 1
			ans += z * (n * (n + 1) // 2 - k * n)
			s -= z * n
			le += z
		z = s - le - 1
		if z * (n * 2 - (z - 1)) < 2 * z * k and z <= n and (le + 1 <= s - z) and (z > 0):
			ans += (z * (n * 2 - (z - 1)) - 2 * z * k) // 2
			le += 1
			s -= z
		print(ans)


import sys
import math
from functools import reduce
import operator as op

def C(n, r=2):
	return n * (n - 1) // 2
	r = min(r, n - r)
	if r == 0:
		return 1
	numer = reduce(op.mul, range(n, n - r, -1))
	denom = reduce(op.mul, range(1, r + 1))
	return numer // denom
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = input().strip().split(' ')
	(n, m, s) = [int(n), int(m), int(s)]
	if n == 2:
		print(s)
		continue
	MaxEdge = C(n - 1, 2)
	if m - 1 <= MaxEdge:
		print(m - 1 + s - (n - 2))
		continue
	result1 = MaxEdge + (m - MaxEdge) * (s - (n - 2))
	extra = s % (n - 1)
	num_min_nodes = n - extra
	num_min_edges = m if num_min_nodes == n else C(num_min_nodes, 2)
	num_max_edges = m - num_min_edges
	min_edge_len = s // (n - 1)
	max_edge_len = min_edge_len + 1
	result0 = num_min_edges * min_edge_len + num_max_edges * max_edge_len
	num_min_nodes = n - 1
	num_min_edges = MaxEdge
	num_max_edges = m - num_min_edges
	max_edge_len = min_edge_len + extra
	result2 = num_min_edges * min_edge_len + num_max_edges * max_edge_len
	print(min(result0, result1, result2))


import sys

def get(n, m, s):
	f = n * (n - 1) // 2 - m
	if f >= n - 1:
		return s - (n - 1) + m
	s -= n - 1
	possibilities = [[(n - 1, s // (n - 1)), (s % (n - 1), 1)], [(1, s)], [(n - 1, s // (n - 1)), (1, s % (n - 1))], [(f, 1), (1, s - f)], [(f, 1), (n - 1, (s - f) // (n - 1)), (1, (s - f) % (n - 1))]]

	def do(possibility):
		ret = m
		checker = 0
		for (i, xi) in possibility:
			if i <= 0 or i >= n:
				return None
			checker += i * xi
			ret += xi * (n * (n - 1) // 2 - (n - i) * (n - i - 1) // 2 - f)
		if checker != s:
			return None
		return ret
	return min((i for i in map(do, possibilities) if i is not None))
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = input().strip().split(' ')
	(n, m, s) = [int(n), int(m), int(s)]
	print(get(n, m, s))


def sm(n):
	return n * (n + 1) // 2

def f(n, m, s):
	if m == n - 1:
		return s
	if s == n - 1:
		return m
	if m - 1 <= sm(n - 2):
		return m + s - n + 1
	x = s - n + 2
	z = sm(n - 2)
	y = m - z
	e = z + y * x
	a = (x - 1) // (n - 1)
	k = a * sm(n - 2) - a * (n - 2) * y
	if k > 0:
		return e
	e += k
	x -= a * (n - 2)
	b = x - a - 2
	if b > 0:
		b = sm(n - 2) - sm(n - b - 2) - b * y
		if b < 0:
			e += b
	return e
for _ in range(int(input())):
	print(f(*map(int, input().split())))


import sys
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = input().strip().split(' ')
	(n, m, s) = [int(n), int(m), int(s)]
	if n * (n - 1) // 2 - m >= n - 2:
		print(s - (n - 1) + m)
	else:
		z = n - 2 - (n * (n - 1) // 2 - m)
		k = n - 1
		s -= n - 1
		ans1 = z * s
		h = s // k
		rem = s - h * k
		ans2 = h * ((k - 1) * (k - 2) // 2 + z) + rem * z
		if rem == 0:
			ans3 = ans2
		else:
			ans3 = h * ((k - 1) * (k - 2) // 2 + z) + z
			rem -= 1
			ans3 += rem * (k - 2 + (k - 1 - rem)) // 2
		print(min(ans1, ans2, ans3) + s + m)


for _ in range(int(input())):
	(N, M, S) = list(map(int, input().split()))
	res = S
	m = M
	mm = M
	M -= N - 1
	W = S // (N - 1)
	big = S - (N - 1) * W
	small = N - big - 1
	if M:
		if M >= (small + 1) * small // 2 - small:
			M -= (small + 1) * small // 2 - small
			res += ((small + 1) * small // 2 - small) * W
		else:
			res += M * W
			M = 0
	if M:
		res += M * (W + 1)
	res2 = S
	m -= N - 1
	if m:
		if m >= (N - 1) * (N - 2) // 2 - (N - 2):
			m -= (N - 1) * (N - 2) // 2 - (N - 2)
			res2 += (N - 1) * (N - 2) // 2 - (N - 2)
		else:
			res2 += m
			m = 0
	if m:
		res2 += m * (S - N + 2)
	res3 = S
	mm -= N - 1
	W = S // (N - 1)
	if mm:
		if mm >= (N - 1) * (N - 2) // 2 - (N - 2):
			mm -= (N - 1) * (N - 2) // 2 - (N - 2)
			res3 += ((N - 1) * (N - 2) // 2 - (N - 2)) * W
		else:
			res3 += mm * W
			mm = 0
	if mm:
		res3 += mm * (W + (S - (N - 1) * W))
	print(min(res, res2, res3))


def asum(x):
	if x < 0:
		return 0
	return x * (x + 1) // 2
q = int(input())
for _ in range(q):
	(n, e, s) = map(int, input().split())
	rem = e - asum(n - 2)
	if rem <= 1:
		print(e - (n - 1) + s)
	else:
		spreadcost = asum(n - 2) + rem
		dumpcost = (n - 1) * rem
		cost = spreadcost
		left = s - (n - 1)
		if dumpcost > spreadcost:
			times = left // (n - 1)
			left -= times * (n - 1)
			cost += times * spreadcost
			dumpcost = left * rem
			spreadcost = asum(n - 2) - asum(n - 2 - (left - 1)) + rem
			if left != 0:
				cost += min(dumpcost, spreadcost)
		else:
			cost += left * rem
		print(cost)


import sys
g = int(input().strip())
for _ in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	nprev = (n - 1) * (n - 2) // 2
	if m <= nprev + 1:
		min_sum = m - 1 + s - n + 2
	else:
		min_sum = s * m
		vers = m - nprev
		extra = s - n + 1
		sm = m + extra * vers
		if sm < min_sum:
			min_sum = sm
		com_num = s // (n - 1)
		extra = s - com_num * (n - 1)
		sm = m * com_num + extra * vers
		if sm < min_sum:
			min_sum = sm
		if s % (n - 1) != 0:
			tr_count = (s // (n - 1) + 1) * (n - 1) - s
			tr_num = s // (n - 1) + 1
			sm = (tr_num - 1) * (tr_count * (tr_count + 1) // 2) + tr_num * (m - tr_count * (tr_count + 1) // 2)
			if sm < min_sum:
				min_sum = sm
	print(min_sum)


import sys

def nCk(n, k):
	result = 1
	for i in range(1, k + 1):
		result = result * (n - i + 1) / i
	return int(result)
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = input().strip().split(' ')
	(n, m, s) = [int(n), int(m), int(s)]
	if (n - 1) * (n - 2) / 2 + 1 >= m:
		BestSoln = s + (m - n + 1)
	else:
		nOnes = int((n - 1) * (n - 2) / 2)
		nMax = m - nOnes
		MaxVal = s - (n - 2)
		THSoln = int(nOnes + nMax * MaxVal)
		LowerVal = int(s // (n - 1))
		HigherVal = LowerVal + 1
		nHigh = s - (n - 1) * LowerVal
		nLow = n - 1 - nHigh
		nLowAdd = nCk(nLow, 2)
		if nLow + nHigh + nLowAdd > m:
			nLowAdd = m - nLow - nHigh
		nHighAdd = m - nLow - nLowAdd - nHigh
		ESoln = (nHigh + nHighAdd) * HigherVal + (nLow + nLowAdd) * LowerVal
		if LowerVal == 1:
			ESoln2 = THSoln
		else:
			LowVal2 = LowerVal
			HighVal2 = s - (n - 2) * LowVal2
			nLow2 = int((n - 1) * (n - 2) / 2)
			nHigh2 = m - nLow2
			ESoln2 = int(nLow2 * LowVal2 + nHigh2 * HighVal2)
		BestSoln = min([THSoln, ESoln, ESoln2])
		Count = 0
		for LowVal3 in range(min([LowerVal, 1]), 0, -1):
			Count += 1
			if Count == 1000:
				break
			HighVal3 = s - (n - 2) * LowVal3
			if HighVal3 < LowVal3:
				break
			nLow3 = int((n - 1) * (n - 2) / 2)
			nHigh3 = m - nLow3
			ESoln3 = int(nLow3 * LowVal3 + nHigh3 * HighVal3)
			if ESoln3 < BestSoln:
				BestSoln = ESoln3
	print(BestSoln)


for _ in range(int(input())):
	(N, M, S) = list(map(int, input().split()))
	res = S
	m = M
	mm = M
	M -= N - 1
	W = S // (N - 1)
	big = S - (N - 1) * W
	small = N - big - 1
	if M:
		if M >= (small + 1) * small // 2 - small:
			M -= (small + 1) * small // 2 - small
			res += ((small + 1) * small // 2 - small) * W
		else:
			res += M * W
			M = 0
	if M:
		res += M * (W + 1)
	res2 = S
	m -= N - 1
	if m:
		if m >= (N - 1) * (N - 2) // 2 - (N - 2):
			m -= (N - 1) * (N - 2) // 2 - (N - 2)
			res2 += (N - 1) * (N - 2) // 2 - (N - 2)
		else:
			res2 += m
			m = 0
	if m:
		res2 += m * (S - N + 2)
	res3 = S
	mm -= N - 1
	W = S // (N - 1)
	if mm:
		if mm >= (N - 1) * (N - 2) // 2 - (N - 2):
			mm -= (N - 1) * (N - 2) // 2 - (N - 2)
			res3 += ((N - 1) * (N - 2) // 2 - (N - 2)) * W
		else:
			res3 += mm * W
			mm = 0
	if mm:
		res3 += mm * (W + (S - (N - 1) * W))
	print(min(res, res2, res3))


import sys

def cums(n):
	if n <= 0:
		return 0
	return n * (n + 1) // 2

def cont(n, m, s):
	f = [1] * (n - 1)
	if True:
		ind = 1
		left = m - (n - 1)
		while left > 0:
			if left - ind < 0:
				f[ind] += left
			else:
				f[ind] += ind
			left -= ind
			ind += 1
		dum = {}

		def best(w, sume, ind):
			if ind == n - 1:
				if sume == s:
					return 0
				else:
					return 10 ** 9 + 7
			if sume >= s:
				return 10 ** 9 + 7
			if (w, sume, ind) not in dum:
				mini = 10 ** 9 + 7
				dumhet = mini
				for wi in range(w, s - sume + 1):
					kand = best(wi, sume + wi, ind + 1) + f[ind] * wi
					if kand < mini:
						dumhet = kand
						mini = kand
				dum[w, sume, ind] = dumhet
			return dum[w, sume, ind]
		besti = 10 ** 9 + 7
		for wi in range(1, s):
			besti = min(besti, best(wi, 0, 0))
		print(besti)
q = int(input().strip())
for _ in range(q):
	(n, m, s) = input().strip().split(' ')
	(n, m, s) = [int(n), int(m), int(s)]
	if m <= 1 + (n - 1) * (n - 2) // 2:
		print(m - (n - 1) + s)
	else:
		k = m - (n - 1) * (n - 2) // 2
		slut = k - 1
		base = cums(n - 2) + k
		goal = s - (n - 1)
		best_move = goal * k
		if cums(n - 2) < k * (n - 2):
			M = goal // (n - 1)
			best_move -= (k * (n - 2) - cums(n - 2)) * M
			goal -= M * (n - 1)
		else:
			print(best_move + base)
			continue
		if goal == 0:
			print(best_move + base)
			continue
		if cums(n - 2) - cums(n - 2 - (goal - 1)) < (goal - 1) * k:
			best_move -= (goal - 1) * k - (cums(n - 2) - cums(n - 2 - (goal - 1)))
		print(best_move + base)


def asum(x):
	if x < 0:
		return 0
	return x * (x + 1) // 2
q = int(input())
for _ in range(q):
	(n, e, s) = map(int, input().split())
	rem = e - asum(n - 2)
	if rem <= 1:
		print(e - (n - 1) + s)
	else:
		spreadcost = asum(n - 2) + rem
		dumpcost = (n - 1) * rem
		cost = spreadcost
		left = s - (n - 1)
		if dumpcost > spreadcost:
			times = left // (n - 1)
			left -= times * (n - 1)
			cost += times * spreadcost
			dumpcost = left * rem
			spreadcost = asum(n - 2) - asum(n - 2 - (left - 1)) + rem
			if left != 0:
				cost += min(dumpcost, spreadcost)
		else:
			cost += left * rem
		print(cost)


import sys
from math import sqrt

def gauss(n):
	return int(0.5 * n * (n + 1))

def geomseq(s, mM):
	D = sqrt(8 * s + 1)
	n1 = int(1 / 2 * (D - 1))
	r = s - gauss(n1)
	nr = mM - n1
	if r < nr:
		r += n1
		nr += 1
		n1 -= 1
	return [n1, r - (nr - 1)]

def f(w, c, mM):
	s = 0
	gw2 = gauss(w[2])
	if c[0] > w[2]:
		s += w[0] * gw2
		s += w[1] * (gauss(c[0]) - gw2)
	else:
		s += w[0] * gw2
	if c[1] == 0:
		return s
	if w[2] < c[0]:
		s += c[1] * w[1]
	else:
		s += c[1] * w[0]
	r = mM - w[1] - 1
	if r <= 0:
		return s
	for i in range(mM - r + 1, mM + 1):
		if i <= w[2]:
			s += w[0]
		else:
			s += w[1]
	return s
	l = 0
	gaussw2 = gauss(w[2])
	s = w[0] * gaussw2
	s += w[1] * (gauss(c[0]) - gaussw2)
	l = w[2] + c[0] - w[2]
	s += c[1] * w[1]
	gaussw2 = gauss(w[2])
	return w[0] * gaussw2 + w[1] * (gauss(c[0]) - gaussw2) + c[1] * w[1]

def halfmat(n):
	return int((n ** 2 - n) / 2 + n)
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = input().strip().split(' ')
	(n, m, s) = [int(n), int(m), int(s)]
	mM = n - 1
	a = s // mM
	b = s % mM
	if m - 1 < halfmat(n - 2):
		c = m - 1
	else:
		c = halfmat(n - 2)
	if m - halfmat(n - 2) > 1:
		d = m - halfmat(n - 2)
	else:
		d = 1
	sw1 = c * 1 + d * (s - mM + 1)
	mi = sw1
	sw2 = c * a + d * (s - (mM - 1) * a)
	if sw2 < mi:
		mi = sw2
	if m - b < halfmat(mM - b):
		e = m - b
	else:
		e = halfmat(mM - b)
	if m - halfmat(mM - b) > b:
		f = m - halfmat(mM - b)
	else:
		f = b
	sw3 = e * a + f * (a + 1)
	if sw3 < mi:
		mi = sw3
	print(mi)


def sm(n):
	return n * (n + 1) // 2

def f(n, m, s):
	if m == n - 1:
		return s
	if s == n - 1:
		return m
	if m - 1 <= sm(n - 2):
		return m + s - n + 1
	x = s - n + 2
	z = sm(n - 2)
	y = m - z
	e = z + y * x
	a = (x - 1) // (n - 1)
	k = a * sm(n - 2) - a * (n - 2) * y
	if k > 0:
		return e
	e += k
	x -= a * (n - 2)
	b = x - a - 2
	if b > 0:
		b = sm(n - 2) - sm(n - b - 2) - b * y
		if b < 0:
			e += b
	return e
for _ in range(int(input())):
	print(f(*map(int, input().split())))


import sys
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = input().strip().split(' ')
	(n, m, s) = [int(n), int(m), int(s)]
	if m <= n * (n - 1) // 2 - (n - 2):
		print(s - (n - 1) + m)
	else:
		n -= 2
		k = m - (n + 1) * n // 2
		s -= n
		ans = (n + 1) * n // 2 + k * s
		le = 1
		if n * (n + 1) // 2 <= k * n and s >= n:
			z = (s - le) // (n + 1)
			while le + z <= s - z * n:
				z += 1
			while le + z > s - z * n and z > 0:
				z -= 1
			ans += z * (n * (n + 1) // 2 - k * n)
			s -= z * n
			le += z
		x = s - le - 1
		if x * (n * 2 - (x - 1)) < 2 * x * k and x <= n and (le + 1 <= s - x) and (x > 0):
			ans += (x * (n * 2 - (x - 1)) - 2 * x * k) // 2
			le += 1
			s -= x
		print(ans)


import sys
for _ in range(int(input().strip())):
	(n_nodes, n_edges, s) = input().strip().split(' ')
	(n_nodes, n_edges, s) = [int(n_nodes), int(n_edges), int(s)]
	n_free_edges = n_edges - n_nodes + 1
	if n_free_edges == 0:
		print(s)
	else:
		n_buckets = n_nodes - 1
		n_free_edges_except_in_last_bucket = (n_buckets - 1) * (n_buckets - 2) // 2
		n_free_edges_in_last_bucket = n_free_edges - n_free_edges_except_in_last_bucket
		if n_free_edges_in_last_bucket <= 0:
			print(s + n_edges - n_buckets)
		elif n_free_edges_in_last_bucket * (n_buckets - 1) <= n_free_edges_except_in_last_bucket:
			print(s + n_free_edges_except_in_last_bucket + n_free_edges_in_last_bucket * (s - n_buckets + 1))
		else:
			weight_each_bucket = s // n_buckets
			one_more_weight_starting_bucket = (n_buckets - s % n_buckets) % n_buckets
			weight_in_last_bucket = weight_each_bucket
			best_weight = s
			if one_more_weight_starting_bucket > 0:
				weight_in_last_bucket += 1
				if one_more_weight_starting_bucket < n_buckets - 1:
					if n_free_edges_except_in_last_bucket - one_more_weight_starting_bucket * (one_more_weight_starting_bucket - 1) // 2 > n_free_edges_in_last_bucket * (n_buckets - one_more_weight_starting_bucket - 1):
						weight_in_last_bucket += n_buckets - one_more_weight_starting_bucket - 1
						one_more_weight_starting_bucket = n_buckets - 1
				best_weight += weight_in_last_bucket * n_free_edges_in_last_bucket + n_free_edges_except_in_last_bucket * (weight_each_bucket + 1) - one_more_weight_starting_bucket * (one_more_weight_starting_bucket - 1) // 2
			else:
				best_weight += weight_in_last_bucket * n_free_edges_in_last_bucket + n_free_edges_except_in_last_bucket * weight_each_bucket
			print(best_weight)


def minMST(n, m, s):
	sg_max = (n - 1) * (n - 2) >> 1
	if sg_max >= m - 1:
		return m - 1 + (s - (n - 2))
	ns = sg_max
	nl = m - ns
	if nl * (n - 1) <= ns:
		sel = 1
		lel = s - (n - 2) * sel
	else:
		sel = s // (n - 1)
		lel = s - (n - 2) * sel
		if 2 * (n - nl) - 1 <= lel - sel:
			k = lel - sel - 1
			lel = sel + 1
			ns = (n - k - 1) * (n - k - 2) >> 1
			nl = m - ns
	return ns * sel + nl * lel
g = int(input())
for g_itr in range(g):
	(n, m, s) = [int(i) for i in input().split()]
	if n > 0:
		print(minMST(n, m, s))


def sm(n):
	return n * (n + 1) // 2

def f(n, m, s):
	if m == n - 1:
		return s
	if s == n - 1:
		return m
	if m - 1 <= sm(n - 2):
		return m + s - n + 1
	x = s - n + 2
	z = sm(n - 2)
	y = m - z
	e = z + y * x
	a = (x - 1) // (n - 1)
	k = a * sm(n - 2) - a * (n - 2) * y
	if k > 0:
		return e
	e += k
	x -= a * (n - 2)
	b = x - a - 2
	if b > 0:
		b = sm(n - 2) - sm(n - b - 2) - b * y
		if b < 0:
			e += b
	return e
for _ in range(int(input())):
	print(f(*map(int, input().split())))


testcase = int(input())
for i in range(testcase):
	(n, m, e) = map(int, input().split())
	if n == 2 or n == 3:
		if m <= 2:
			print(e)
		else:
			print(2 * e - e // 2)
		continue
	leftSum = (n - 2) * (n - 3) // 2
	x = m - (n - 1) - leftSum
	result = e + leftSum
	bigEdge = e - (n - 2)
	if m < n - 1 + leftSum:
		print(e + m - n + 1)
		continue
	if x * (n - 2) >= leftSum:
		result = e + e // (n - 1) * leftSum
		bigEdge = e - e // (n - 1) * (n - 2)
	extra = x * bigEdge
	k = e % (n - 1) - 1
	if k > 0:
		newExtra = x * (bigEdge - k) + (n - 3) * k - k * (k - 1) // 2
		extra = min(extra, newExtra)
	print(result + extra)


import sys
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = input().strip().split(' ')
	(n, m, s) = [int(n), int(m), int(s)]
	if m <= (n - 1) * (n - 2) // 2 + 1:
		print(m + s - n + 1)
	else:
		s -= n - 1
		e = m - (n - 1) * (n - 2) // 2
		mnc = (s + n - 2) // (n - 1)
		ans = 1e+42
		s -= mnc
		for A in [0, s // (n - 2), s // (n - 2) - 1]:
			for B in [0, n - 3, (s - A * (n - 2)) % (n - 2)]:
				x = A * (n - 2) + B
				if 0 <= x <= s:
					ans = min(ans, (s - x + mnc) * e + (n - 1) * (n - 2) // 2 * A + B * (B - 1) // 2 + B * (n - B - 1))
		print(ans + m)


import math
import os
import random
import re
import sys

def alloc_onehi(s, n, max_edges, mst_edges, possible_edges, edges_to_add):
	lo_edge_cost = 1
	hi_edge_cost = s - (mst_edges - 1)
	if hi_edge_cost > 1:
		possible_hicost_edges = n - 2
	else:
		possible_hicost_edges = 0
	possible_locost_edges = possible_edges - possible_hicost_edges
	assert possible_edges == possible_locost_edges + possible_hicost_edges
	return (possible_locost_edges, possible_hicost_edges, lo_edge_cost, hi_edge_cost)

def alloc_level(s, n, max_edges, mst_edges, possible_edges, edges_to_add):
	lo_edge_cost = math.floor(s // mst_edges)
	hi_edge_cost = lo_edge_cost + 1
	hi_cost_vs = s % mst_edges
	lo_cost_vs = mst_edges - hi_cost_vs
	possible_locost_edges = lo_cost_vs * (lo_cost_vs - 1) // 2
	possible_hicost_edges = hi_cost_vs * (hi_cost_vs - 1) // 2 + lo_cost_vs * hi_cost_vs
	assert possible_edges == possible_locost_edges + possible_hicost_edges
	return (possible_locost_edges, possible_hicost_edges, lo_edge_cost, hi_edge_cost)

def alloc_hybrid(s, n, max_edges, mst_edges, possible_edges, edges_to_add):
	lo_edge_cost = math.floor(s // mst_edges)
	remainder = s % (n - 1)
	hi_edge_cost = lo_edge_cost + remainder
	if remainder > 0:
		possible_hicost_edges = n - 2
	else:
		possible_hicost_edges = 0
	possible_locost_edges = possible_edges - possible_hicost_edges
	assert possible_edges == possible_locost_edges + possible_hicost_edges
	return (possible_locost_edges, possible_hicost_edges, lo_edge_cost, hi_edge_cost)

def graph_cost(s, edges_to_add, possible_locost_edges, possible_hicost_edges, lo_edge_cost, hi_edge_cost):
	g_cost = s
	if edges_to_add > possible_locost_edges:
		hicost_edges = edges_to_add - possible_locost_edges
		g_cost += hicost_edges * hi_edge_cost
		edges_to_add -= hicost_edges
	if edges_to_add <= possible_locost_edges:
		g_cost += edges_to_add * lo_edge_cost
	return int(g_cost)
g = int(input())
for g_itr in range(g):
	nms = input().split()
	n = int(nms[0])
	m = int(nms[1])
	s = int(nms[2])
	max_edges = n * (n - 1) // 2
	mst_edges = n - 1
	possible_edges = max_edges - mst_edges
	edges_to_add = m - mst_edges
	(possible_locost_edges, possible_hicost_edges, lo_edge_cost, hi_edge_cost) = alloc_onehi(s, n, max_edges, mst_edges, possible_edges, edges_to_add)
	onehi_g = graph_cost(s, edges_to_add, possible_locost_edges, possible_hicost_edges, lo_edge_cost, hi_edge_cost)
	(possible_locost_edges, possible_hicost_edges, lo_edge_cost, hi_edge_cost) = alloc_level(s, n, max_edges, mst_edges, possible_edges, edges_to_add)
	level_g = graph_cost(s, edges_to_add, possible_locost_edges, possible_hicost_edges, lo_edge_cost, hi_edge_cost)
	(possible_locost_edges, possible_hicost_edges, lo_edge_cost, hi_edge_cost) = alloc_hybrid(s, n, max_edges, mst_edges, possible_edges, edges_to_add)
	hybrid_g = graph_cost(s, edges_to_add, possible_locost_edges, possible_hicost_edges, lo_edge_cost, hi_edge_cost)
	print(min(onehi_g, min(level_g, hybrid_g)))


testcase = int(input())
for i in range(testcase):
	(n, m, e) = map(int, input().split())
	leftSum = (n - 2) * (n - 3) // 2
	x = m - (n - 1) - leftSum
	result = e + leftSum
	bigEdge = e - (n - 2)
	if m < n - 1 + leftSum:
		print(e + m - n + 1)
		continue
	if x * (n - 2) >= leftSum:
		result = e + e // (n - 1) * leftSum
		bigEdge = e - e // (n - 1) * (n - 2)
	extra = x * bigEdge
	k = e % (n - 1) - 1
	if k > 0:
		newExtra = x * (bigEdge - k) + (n - 3) * k - k * (k - 1) // 2
		extra = min(extra, newExtra)
	print(result + extra)


import sys
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = input().strip().split(' ')
	(n, m, s) = [int(n), int(m), int(s)]
	if m <= (n - 1) * (n - 2) // 2 + 1:
		print(m + s - n + 1)
	else:
		s -= n - 1
		e = m - (n - 1) * (n - 2) // 2
		mnc = (s + n - 2) // (n - 1)
		ans = 1e+42
		s -= mnc
		for A in [0, s // (n - 2), s // (n - 2) - 1]:
			for B in [0, n - 3, (s - A * (n - 2)) % (n - 2)]:
				x = A * (n - 2) + B
				if 0 <= x <= s:
					ans = min(ans, (s - x + mnc) * e + (n - 1) * (n - 2) // 2 * A + B * (B - 1) // 2 + B * (n - B - 1))
		print(ans + m)


import sys
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = input().strip().split(' ')
	(n, m, s) = [int(n), int(m), int(s)]
	if m <= (n - 1) * (n - 2) // 2 + 1:
		print(m + s - n + 1)
	else:
		s -= n - 1
		e = m - (n - 1) * (n - 2) // 2
		mnc = (s + n - 2) // (n - 1)
		ans = 1e+42
		s -= mnc
		for A in [0, s // (n - 2), s // (n - 2) - 1]:
			for B in [0, n - 3, (s - A * (n - 2)) % (n - 2)]:
				x = A * (n - 2) + B
				if 0 <= x <= s:
					ans = min(ans, (s - x + mnc) * e + (n - 1) * (n - 2) // 2 * A + B * (B - 1) // 2 + B * (n - B - 1))
		print(ans + m)


def sm(n):
	return n * (n + 1) // 2

def f(n, m, s):
	if m == n - 1:
		return s
	if s == n - 1:
		return m
	if m - 1 <= sm(n - 2):
		return m + s - n + 1
	x = s - n + 2
	z = sm(n - 2)
	y = m - z
	e = z + y * x
	a = (x - 1) // (n - 1)
	k = a * sm(n - 2) - a * (n - 2) * y
	if k > 0:
		return e
	e += k
	x -= a * (n - 2)
	b = x - a - 2
	if b > 0:
		b = sm(n - 2) - sm(n - b - 2) - b * y
		if b < 0:
			e += b
	return e
for _ in range(int(input())):
	print(f(*map(int, input().split())))


import math
import os
import random
import re
import sys
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = input().strip().split(' ')
	(n, m, s) = [int(n), int(m), int(s)]
	if m <= (n - 1) * (n - 2) // 2 + 1:
		print(m + s - n + 1)
	else:
		s -= n - 1
		e = m - (n - 1) * (n - 2) // 2
		mnc = (s + n - 2) // (n - 1)
		ans = 1e+42
		s -= mnc
		for A in [0, s // (n - 2), s // (n - 2) - 1]:
			for B in [0, n - 3, (s - A * (n - 2)) % (n - 2)]:
				x = A * (n - 2) + B
				if 0 <= x <= s:
					ans = min(ans, (s - x + mnc) * e + (n - 1) * (n - 2) // 2 * A + B * (B - 1) // 2 + B * (n - B - 1))
		print(ans + m)


import sys
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = input().strip().split(' ')
	(n, m, s) = [int(n), int(m), int(s)]
	if m <= (n - 1) * (n - 2) // 2 + 1:
		print(m + s - n + 1)
	else:
		s -= n - 1
		e = m - (n - 1) * (n - 2) // 2
		mnc = (s + n - 2) // (n - 1)
		ans = 1e+42
		s -= mnc
		for A in [0, s // (n - 2), s // (n - 2) - 1]:
			for B in [0, n - 3, (s - A * (n - 2)) % (n - 2)]:
				x = A * (n - 2) + B
				if 0 <= x <= s:
					ans = min(ans, (s - x + mnc) * e + (n - 1) * (n - 2) // 2 * A + B * (B - 1) // 2 + B * (n - B - 1))
		print(ans + m)


import sys
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


import math
import os
import random
import re
import sys
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


import math
import os
import random
import re
import sys
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


import math
import os
import random
import re
import sys
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


import math
import os
import random
import re
import sys
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


import math
import os
import random
import re
import sys
g = int(input())
for g_itr in range(g):
	nms = input().split()
	n = int(nms[0])
	m = int(nms[1])
	s = int(nms[2])
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


import math
import os
import random
import re
import sys
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


import math
import os
import random
import re
import sys
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


import math
import os
import random
import re
import sys
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


import math
import os
import random
import re
import sys
g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))


g = int(input().strip())
for a0 in range(g):
	(n, m, s) = map(int, input().strip().split(' '))
	n2 = (n * n - 3 * n + 4) // 2
	if n == 2:
		print(s)
	elif m <= n2:
		print(s + m - n + 1)
	else:
		a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1
		x = n - 1 - s % (n - 1)
		y = s % (n - 1)
		div = s // (n - 1)
		t = x * (x + 1) // 2
		a2 = t * div
		a2 += max(0, (div + 1) * (m - t))
		rem = s - (n - 2) * div
		kant = (n - 2) * (n - 1) // 2
		a3 = kant * div + (m - kant) * rem
		print(min(a1, a2, a3))