Tracy gives Charlie a [Directed Acyclic Graph] with N vertices. Among these N vertices, K vertices are *sources*, and L vertices are *sinks*. 

Find out the maximum number of edges this graph can have.

Note:
A *source* is a vertex with no incoming edge.
A *sink* is a vertex with no outgoing edge.
A vertex can be both, a source, and a sink.

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

- First line will contain T, number of test cases. Then the test cases follow. 
- Each test case contains of a single line of input, three space-separated integers N, K, and L - the number of vertices, the number of sources and the number of sinks respectively.

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

- For each test case, output in a single line, the maximum number of edges this graph can have.

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

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 10^{9}$
$1 ≤ K < N$
$1 ≤ L < N$

----- Sample Input 1 ------ 
2
3 1 1
5 3 3

----- Sample Output 1 ------ 
3
4

----- explanation 1 ------ 
Test case $1$: Assume that the vertices are numbered $1,2,$ and $3$. Let $1$ be a source and $3$ be a sink. The edges of a possible DAG are $1\rightarrow 2, 2\rightarrow 3,$ and $1\rightarrow 3$.

The number of edges in this graph are $3$. It can be shown that this is the maximum number of edges possible under given constraints.

Test case $2$: Assume that the vertices are numbered $1,2,3,4,$ and $5$. Let $1,2,$ and $3$ be sources and $3, 4, $ and $5$ be  sinks. The edges of a possible DAG are $1\rightarrow 4, 2\rightarrow 4, 1\rightarrow 5$ and $2\rightarrow 5$.

The number of edges in this graph are $4$. It can be shown that this is the maximum number of edges possible under given constraints.

Difficulty: MEDIUM_HARD
Tags: Combinatorics

Mathematics

Starter code:

Solutions:
for _ in range(int(input())):
	(n, k, l) = tuple(map(int, input().split()))
	v = n - k - l
	if v < 0:
		k += v
		l += v
		v = 0
	print(k * l + k * v + l * v + v * (v - 1) // 2)


case = int(input())
for _ in range(case):
	(n, k, l) = map(int, input().split(' '))
	source = 0
	central = 0
	sink = 0
	if k + l <= n:
		total = n
		source = k
		central = n - (k + l)
		sink = l
		res = source * (total - source) + central * sink + central * (central - 1) // 2
		print(res)
	else:
		diff = k + l - n
		source = k - diff if k - diff > 0 else 0
		sink = l - diff if l - diff > 0 else 0
		res = source * sink
		print(res)


t = int(input())
for i in range(0, t):
	(n, k, l) = map(int, input().split())
	if k + l == n:
		print(k * l)
	elif k + l > n:
		print((n - k) * (n - l))
	else:
		z = n - k - l
		print(k * (n - k) + z * l + z * (z - 1) // 2)


import math
for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	if k + l >= n:
		print((n - k) * (n - l))
	else:
		total = 0
		rem = n - k - l
		total += rem * (k + l) + rem * (rem - 1) // 2 + k * l
		print(total)


num_tests = int(input())
for t in range(num_tests):
	lst = [int(x) for x in input().split(' ')]
	(nodes, sources, sinks) = lst
	source_sinks = max(0, sources + sinks - nodes)
	sources -= source_sinks
	sinks -= source_sinks
	reg = max(nodes - sources - sinks - source_sinks, 0)
	ans = reg * (reg - 1) // 2
	ans += sources * reg
	ans += sinks * reg
	ans += sources * sinks
	print(ans)


goals = int(input())
for distractions in range(goals):
	(aim, wife, life) = map(int, input().split())
	death = 0
	if wife + life <= aim:
		final = aim - (wife + life)
		death += wife * (final + life)
		death += final * life
		death += final * (final - 1) // 2
	else:
		final = wife + life - aim
		wife -= final
		life -= final
		final = 0
		death += wife * (final + life)
		death += final * life
		death += final * (final + 1) // 2
	print(death)


for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	result = 0
	if k + l >= n:
		dif = abs(n - k - l)
		k = k - dif
		l = l - dif
		print(k * l)
	else:
		m = n - k - l
		msm = m * (m - 1) // 2
		print(k * m + k * l + m * l + msm)


T = int(input())
for i in range(T):
	N = list(map(int, input().split()))
	Source = N[1]
	Sink = N[2]
	Middle = 0
	if N[0] > N[1] + N[2]:
		Middle = N[0] - N[1] - N[2]
	Node_Sink_Source = 0
	if Middle == 0:
		Node_Sink_Source = abs(N[0] - N[1] - N[2])
	Tot = 0
	if Node_Sink_Source != 0:
		Tot = (N[0] - N[1]) * (N[0] - N[2])
		print(Tot)
	else:
		Tot = N[1] * N[2] + N[1] * Middle + Middle * N[2] + Middle * (Middle - 1) // 2
		print(Tot)


for i in range(int(input())):
	(n, a, b) = map(int, input().split())
	if a + b >= n:
		print((n - b) * (n - a))
	else:
		x = n - a - b
		s = x * (x - 1) // 2
		print(s + x * a + x * b + a * b)


tst = int(input())
for t in range(tst):
	(k, l, m) = map(int, input().split(' '))
	x = k - (l + m)
	if x < 0:
		l += x
		m += x
	ans = m * l
	if x > 0:
		ans = ans + x * (l + m) + x * (x - 1) // 2
	print(ans)


t = int(input())
while t > 0:
	(n, l, k) = map(int, input().split())
	rem = n - (l + k)
	if rem < 0:
		l = l + rem
		k = k + rem
		rem = 0
	s = 0
	s = l * (k + rem)
	s += rem * k
	s += rem * (rem - 1) // 2
	print(s)
	t -= 1


import sys
for _ in range(int(input())):
	(n, k, l) = [int(i) for i in input().split()]
	rep = max(0, k + l - n)
	(n, k, l) = (n - rep, k - rep, l - rep)
	res = (n - k - l) * (n - k - l - 1) // 2 + k * (n - k - l) + (n - k - l) * l + k * l
	sys.stdout.write(str(res) + '\n')
	pass


for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	if k + l > n:
		common = k + l - n
		n -= common
		k -= common
		l -= common
	print(k * (n - k) + (n - k - l) * (n - k - l - 1) // 2 + (n - k - l) * l)


def fact(n):
	if n == 1 or n == 0:
		return 1
	s = 1
	for i in range(1, n + 1):
		s *= i
	return s
for _ in range(int(input())):
	(n, s, e) = [int(i) for i in input().split()]
	totalS = s
	totalE = e
	ee = n - e + 1
	if s >= ee:
		ss = s
		s = ee - 1
		e = n - ss
	remaining = totalE + totalS
	remaining = n - min(remaining, n)
	total = s * e + (e + s) * remaining
	if remaining > 1:
		total += remaining * (remaining - 1) // 2
	print(total)


def src_and_snk(n, k, l):
	if k + l > n:
		both = k + l - n
		srcs = k - both
		snks = l - both
		return srcs * snks
	else:
		neither = n - (k + l)
		return k * l + (k + l) * neither + (neither - 1) * neither // 2
tests = int(input())
for test in range(tests):
	[n, k, l] = [int(i) for i in input().split(' ')]
	output = src_and_snk(n, k, l)
	print(output)


t = int(input())
for _ in range(t):
	(n, k, l) = list(map(int, input().split()))
	x = k + l
	p = n - x
	if p < 0:
		l = l + p
		k = k + p
		print(k * l)
	elif p > 0:
		xk = l + p
		print(k * xk + p * l + p * (p - 1) // 2)
	else:
		print(k * l)


for i in range(int(input())):
	(N, K, L) = map(int, input().split())
	N = N - L - K
	if N < 0:
		N = abs(N)
		L = L - N
		K = K - N
		N = 0
	print(K * (L + N) + N * L + N * (N - 1) // 2)


for _ in range(int(input())):
	(N, K, L) = map(int, input().split())
	N -= K + L
	ans = 0
	if N < 0:
		N = abs(N)
		L = L - N
		K = K - N
		N = 0
	ans = K * (L + N) + N * L + N * (N - 1) // 2
	print(ans)


for _ in range(int(input())):
	(t, source, sink) = map(int, input().split())
	l = t - (source + sink)
	other = 0
	if l < 0:
		source += l
		sink += l
	else:
		other = l
	count = source * other + source * sink + other * sink + other * (other - 1) // 2
	print(count)


for t in range(int(input())):
	(n, k, l) = map(int, input().split())
	if l + k <= n:
		c = n - (l + k)
		print(k * l + k * c + c * l + c * (c - 1) // 2)
	else:
		x = k - (l + k - n)
		y = l - (l + k - n)
		print(x * y)


for i in range(int(input())):
	(n, k, l) = map(int, input().split())
	n = n - l - k
	if n < 0:
		n = abs(n)
		l = l - n
		k = k - n
		n = 0
	print(k * (n + l) + n * l + n * (n - 1) // 2)


t = int(input())
for i in range(t):
	(n, k, l) = map(int, input().split())
	if k + l > n:
		x = k + l - n
		ans = (k - x) * (l - x)
	else:
		x = n - (l + k)
		ans = k * l + k * x + l * x + x * (x - 1) // 2
	print(ans)


t = int(input())
for inp in range(t):
	(n, k, l) = [int(i) for i in input().split()]
	if n - (k + l) == 0:
		max_edges = k * l
	elif n - (k + l) > 0:
		v = n - (k + l)
		max_edges = k * l + k * v + v * l + v * (v - 1) // 2
	else:
		w = k + l - n
		k -= w
		l -= w
		max_edges = k * l
	print(max_edges)


t = int(input())
for _ in range(t):
	(n, k, l) = map(int, input().split())
	if k + l >= n:
		nn = k + l - n
		print(max((k - nn) * (l - nn), 0))
	else:
		ans = k * l + (n - k - l) * (k + l)
		print(ans + (n - k - l - 1) * (n - k - l) // 2)


for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	x = n - k - l
	if x > 0:
		print(x * (x - 1) // 2 + k * l + x * (k + l))
	else:
		x = -1 * x
		k -= x
		l -= x
		print(k * l)


import sys
input = sys.stdin.readline

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

def inlt():
	return list(map(int, input().split()))

def insr():
	return input().strip()

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

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
ans = []
for _ in range(inp()):
	(N, K, L) = inlt()
	if N >= K + L:
		(st, en) = (L - 1, N - K - 1)
		an = K * (N - K) + en * (en + 1) // 2 - st * (st + 1) // 2
	else:
		an = (N - L) * (N - K)
	ans.append(an)
outplt(ans)


t = int(input())
ans = []
for i in range(t):
	(n, k, l) = map(int, input().split())
	m = n - (k + l)
	if m < 0:
		k += m
		l += m
		n += m
	mid = n - (k + l)
	print(k * l + (k + l) * mid + mid * (mid - 1) // 2)


for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	(s, mid) = (0, 0)
	if n < k + l:
		s = k + l - n
		n = n - s
		k = k - s
		l = l - s
	mid = n - (k + l)
	print(k * l + (k + l) * mid + mid * (mid - 1) // 2)


T = int(input())
for _ in range(T):
	(N, source, sink) = map(int, input().split())
	if source + sink > N:
		R = source + sink - N
		(N, source, sink) = (N - R, source - R, sink - R)
	mid = N - (source + sink)
	print(source * sink + (source + sink) * mid + mid * (mid - 1) // 2)


testcase = int(input())
for _ in range(testcase):
	(n, k, l) = map(int, input().split())
	d = n - (k + l)
	if d > 0:
		print(l * k + d * k + d * l + (d * d - d) // 2)
	else:
		print((l + d) * (k + d))


t = int(input())
for i in range(t):
	(n, k, l) = map(int, input().split())
	if k + l <= n:
		source = k
		sink = l
		both = n - (k + l)
	else:
		y = k + l - n
		k -= y
		l -= y
		n -= y
		source = k
		sink = l
		both = 0
	print(source * (n - source) + sink * (n - sink) - source * sink + both * (both - 1) // 2)


for i in range(int(input())):
	(n, k, l) = map(int, input().split())
	n1 = n - (k + l)
	if n1 < 0:
		n1 *= -1
		n -= n1
		k -= n1
		l -= n1
		p = n * (n - 1) // 2
		p -= k * (k - 1) // 2 + l * (l - 1) // 2
		print(p)
	else:
		p = n * (n - 1) // 2
		p -= k * (k - 1) // 2 + l * (l - 1) // 2
		print(p)


from decimal import Decimal
for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	res = k + l - n
	if res >= 0:
		k -= res
		l -= res
		print(k * l)
	else:
		gap = Decimal(n - k - l)
		ad = gap * (gap - 1) / 2
		ans = k * l + gap * (k + l) + ad
		print(ans)


for i in range(int(input())):
	(ve, so, si) = map(int, input().split())
	if so + si > ve:
		y = so + si - ve
		ve = ve - y
		so = so - y
		si = si - y
	ans = so * (ve - so) + (ve - so - si) * si + (ve - si - so) * (ve - si - so - 1) // 2
	print(ans)


t = int(input())
for _ in range(t):
	(n, k, l) = list(map(int, input().split()))
	rem = n - k - l
	if k + l > n:
		temp = k + l - n
		k -= temp
		l -= temp
		rem = 0
	a = k * (l + rem) + rem * l
	a += rem * (rem - 1) // 2
	print(a)


def soln(n, sc, si):
	if n < sc + si:
		temp = sc + si - n
		sc -= temp
		si -= temp
		return sc * si
	extra = n - (sc + si)
	res = sc * (extra + si) + extra * si + extra * (extra - 1) // 2
	return res
for _ in range(int(input())):
	(n, sc, si) = map(int, input().split())
	print(soln(n, sc, si))


def solve(a, b, c):
	t = b * (a - b) + c * (a - c) - b * c
	return t
for _ in range(int(input())):
	(n, k, l) = map(int, input().split(' '))
	if n - (k + l) > 0:
		z = n - k - l
		a = solve(n, k, l)
		a += z * (z - 1) // 2
		print(a)
	else:
		y = abs(n - k - l)
		a = solve(n - y, k - y, l - y)
		print(a)


import decimal
t = int(input())
for tr in range(t):
	(n, k, l) = list(map(int, input().split()))
	both = k + l - n
	if both >= 0:
		k -= both
		l -= both
		print(k * l)
	else:
		gap = decimal.Decimal(n - k - l)
		add = gap * (gap - 1) / 2
		res = k * l + gap * (k + l) + add
		print(res)


t = int(input())
for tr in range(t):
	(n, k, l) = list(map(int, input().split()))
	both = k + l - n
	if k == 1 and l == 1:
		print(n * (n - 1) // 2)
	elif both >= 0:
		k -= both
		l -= both
		print(k * l)
	else:
		gap = n - k - l
		add = int(gap * (gap - 1) // 2)
		print(k * l + gap * (k + l) + add)


t = int(input())
for _ in range(t):
	(n, k, l) = map(int, input().split())
	flag = 1
	if k + l > n:
		flag = 0
		r = k + l - n
		k -= r
		l -= r
		n -= r
	ans = k * (n - k)
	if flag == 1:
		ans += (n - k - l) * l + (n - k - l) * (n - k - l - 1) // 2
	print(ans)


for _ in range(int(input())):
	(n, k, l) = map(int, input().split())
	n = n - (l + k)
	if n < 0:
		n = abs(n)
		l = l - n
		k = k - n
		n = 0
	ans = k * (n + l) + n * l + n * (n - 1) // 2
	print(ans)


T = int(input())
for t in range(T):
	(n, k, l) = map(int, input().split(' '))
	z = n - (k + l)
	if z < 0:
		k += z
		l += z
	ans = l * k
	if z > 0:
		ans = ans + z * (k + l) + z * (z - 1) // 2
	print(ans)


def solve(n, sources, sinks):
	if sources + sinks <= n:
		extra = n - (sources + sinks)
		total = sources * (sinks + extra)
		if extra > 0:
			total += extra * sinks
			total += (extra - 1) * extra // 2
		return total
	shared = sources + sinks - n
	sources -= shared
	sinks -= shared
	return sources * sinks
for _ in range(int(input())):
	(n, sources, sinks) = list(map(int, input().split()))
	print(solve(n, sources, sinks))


t = int(input())
for tr in range(t):
	(n, k, l) = list(map(int, input().split()))
	both = k + l - n
	if k == 1 and l == 1:
		print(n * (n - 1) // 2)
	elif both >= 0:
		k -= both
		l -= both
		print(k * l)
	else:
		gap = n - k - l
		add2 = int(gap * (gap - 1) / 2)
		add = int(gap * (gap - 1) // 2)
		if add != add2 and gap < 1 * 10 ** 8 + 3 * 10 ** 7 + 4 * 10 ** 6 + 2 * 10 ** 5 + 2 * 10 ** 4:
			sdfg
		print(k * l + gap * (k + l) + add)


t = int(input())
while t != 0:
	(n, k, l) = map(int, input().split())
	z = k + l - n
	if z < 0:
		p = (n * (n - 1) - k * (k - 1) - l * (l - 1)) // 2
		print(p)
	else:
		n = n - z
		k = k - z
		l = l - z
		q = (n * (n - 1) - k * (k - 1) - l * (l - 1)) // 2
		print(q)
	t = t - 1


t = int(input())
for tr in range(t):
	(n, k, l) = list(map(int, input().split()))
	both = k + l - n
	if k == 1 and l == 1:
		print(n * (n - 1) // 2)
	elif both >= 0:
		k -= both
		l -= both
		print(k * l)
	else:
		gap = n - k - l
		add2 = int(gap * (gap - 1) / 2)
		add = int(gap * (gap - 1) // 2)
		if add != add2 and gap < 9 * 10 ** 7:
			sdfg
		print(k * l + gap * (k + l) + add)


for _ in range(int(input())):
	(n, so, si) = map(int, input().split())
	a = so + si
	s = 0
	if so > n or si > n:
		print(0)
	elif a > n:
		a = a - n
		so -= a
		si -= a
	elif a < n:
		k = n - a
		s = so * k + k * si + k * (k - 1) // 2
	print(so * si + s)