Chef is a high-ranked army officer and he has been given the job to train the army.

The army consists of N soldiers where each soldier has 3 parameters:
*Attack points*: A_{i} where (0< A_{i} < 1000);
*Defense points*: (1000-A_{i});
*Soldier type*: ATTACK or DEFENSE.

For the whole army:
*Attack value* of the army is defined as the sum of *attack points* of all ATTACK type soldiers.
*Defense value* of the army is defined as the sum of *defense points* of all DEFENSE type soldiers.
*Rating* of the army is defined as the product of *Attack value* and *Defense value* of the army. 

Assign the *soldier type* to each of the soldiers to maximize the *rating* of the army. Print the maximum *rating*.

NOTE: The output may exceed the range of a 32-bit integer.  
Remember to use 64-bit data types, such as long long in C++.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N — the number of soldiers in the army.
- The next line contains the array A — where A_{i} denotes the *attack points* of the i^{th} soldier.

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

For each test case, output on a new line the maximum possible *rating* that can be achieved.

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

$1 ≤ T ≤ 100$
$2 ≤ N ≤ 1000$
$0 < A_{i} < 1000$
- Sum of $N$ over all test cases does not exceed $2000$.

----- Sample Input 1 ------ 
4
2
500 500
3
500 500 500
4
100 800 300 500
4
300 700 800 200

----- Sample Output 1 ------ 
250000
500000
2080000
2250000

----- explanation 1 ------ 
Test case $1$: Soldier $1$ should be used for ATTACK while soldier $2$ should be used for DEFENSE. Thus, the *attack value* as well as the *defense value* equals $500$. The *rating* $=500\cdot 500 = 250000$. It can be proven that this is the maximum possible *rating* that we can achieve for the given army.

Test case $2$:
- Soldier $1$ and $2$ should be used for ATTACK. So, *attack value* $=500+500=1000$
- Soldier $3$ should be used for DEFENSE. So, *defense value* $=(1000-500)=500$

So, *rating* $=1000 \cdot 500=500000$. This is the maximum possible *rating* that we can achieve for the given army.

Test case $3$:
- Soldier $2$ and $4$ should be used for ATTACK. So, *attack value* $=800+500=1300$
- Soldier $1$ and $3$ should be used for DEFENSE. So, *defense value* $=(1000-100)+(1000-300)=1600$

So, *rating* $=1300 \cdot 1600=2080000$. This is the maximum possible *rating* that we can achieve for the given army.

Test case $4$:
- Soldier $2$ and $3$ should be used for ATTACK. So, *attack value* $=700+800=1500$
- Soldier $1$ and $4$ should be used for DEFENSE. So, *defense value* $=(1000-300)+(1000-200)=1500$

So, *rating* $=1500 \cdot 1500=2250000$. This is the maximum possible *rating* that we can achieve for the given army.

Difficulty: MEDIUM_HARD
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
for iin in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	maxi = 0
	for i in range(n):
		x = sum(a[i:])
		y = sum(a[:i])
		z = 1000 * i - y
		maxi = max(maxi, x * z)
	print(maxi)


for i in range(int(input())):
	n = int(input())
	atk = list(map(int, input().split()))
	atk.sort()
	max1 = 0
	for i in range(n):
		a = sum(atk[i:])
		sum1 = sum(atk[:i])
		b = i * 1000 - sum1
		max1 = max(max1, a * b)
	print(max1)


t = int(input())
for i in range(t):
	n = int(input())
	attack = [int(i) for i in input().split()]
	attack.sort()
	max1 = 0
	for i in range(n):
		a = sum(attack[i:])
		d = i * 1000 - sum(attack[:i])
		max1 = max(max1, a * d)
	print(max1)


for _ in range(int(input())):
	n = int(input())
	attac = [int(i) for i in input().split()]
	attac.sort()
	maxx = 0
	for i in range(n):
		a = sum(attac[i:])
		d = i * 1000 - sum(attac[:i])
		maxx = max(maxx, a * d)
	print(maxx)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	s = sum(a)
	ans = float('-inf')
	d = 0
	for i in range(n - 1):
		d += 1000 - a[i]
		s -= a[i]
		ans = max(ans, d * s)
	print(ans)


ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)
t = ri()
for test in range(t):
	n = ri()
	l = rl()
	l.sort(reverse=True)
	total = 0
	for i in l:
		total += i
	s = 0
	final = 0
	for i in range(n):
		final = max(final, s * (1000 * (n - i) - (total - s)))
		s += l[i]
	print(final)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	l.reverse()
	totalsum = sum(l)
	s = 0
	ans = 0
	for i in range(n):
		ans = max(ans, s * (1000 * (n - i) - (totalsum - s)))
		s += l[i]
	print(ans)


import math

def solve(num, l):
	l.sort()
	attack = [l[num - 1]]
	defense = [1000 - l[0]]
	for i in range(1, num - 1):
		ty1 = (sum(attack) + l[i]) * sum(defense)
		ty2 = sum(attack) * (sum(defense) + 1000 - l[i])
		if ty1 >= ty2:
			attack.append(l[i])
		else:
			defense.append(1000 - l[i])
	return sum(attack) * sum(defense)

def isprime(num):
	for i in range(2, int(pow(num, 1 / 2) + 1)):
		if num % i == 0:
			return False
	return True

def compute(num, l):
	l.sort()
	l.reverse()
	maxi = 0
	for r in range(0, num):
		pro = sum(l[0:r + 1]) * ((num - r - 1) * 1000 - sum(l[r + 1:num]))
		if pro > maxi:
			maxi = pro
	return maxi
n = int(input())
results = []
for i in range(0, n):
	num = int(input())
	l = list(map(int, input().split()))
	out = compute(num, l)
	results.append(out)
for j in results:
	print(j)


for test in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	one = [0]
	two = [0]
	l.sort()
	s1 = 0
	s2 = 0
	for i in l[::-1]:
		s1 += i
		one.append(s1)
	for j in l:
		s2 += 1000 - j
		two.append(s2)
	two.reverse()
	M = 0
	for i in range(n + 1):
		M = max(M, one[i] * two[i])
	print(M)


T = int(input())
while T > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	k = 0
	attack = [0] * (n - 1)
	defence = [0] * (n - 1)
	defence[0] = 1000 - arr[0]
	for i in range(1, n - 1):
		defence[i] = 1000 - arr[i] + defence[i - 1]
	attack[-1] = arr[-1]
	for i in range(-2, -n, -1):
		attack[i] = arr[i] + attack[i + 1]
	max = 0
	for i in range(n - 1):
		rank = attack[i] * defence[i]
		if rank > max:
			max = rank
	print(max)
	T -= 1


from collections import Counter
import numpy as np

def tryout_army(stats_soldiers):
	all_stats = Counter(stats_soldiers)
	possible_values = list(all_stats.keys())
	possible_values.sort()
	max_stats = 0
	defense = 0
	attack = sum(stats_soldiers)
	exit_loop = 0
	value_track_i = 0
	count_tracker = 1
	while exit_loop == 0:
		value = possible_values[value_track_i]
		if all_stats[value] >= count_tracker:
			count_tracker += 1
			defense += 1000 - value
			attack -= value
			if defense * attack < max_stats:
				exit_loop = 1
			else:
				max_stats = defense * attack
		else:
			count_tracker = 1
			value_track_i += 1
	return max_stats
T = int(input())
for tc in range(T):
	nb_soldiers = int(input())
	stats = list(map(int, input().split(' ')))
	print(tryout_army(stats))


(ans, c) = ([], 1000)
for _ in range(int(input())):
	N = int(input())
	A = sorted([int(x) for x in input().split()])
	at = sum(A)
	(df, an) = (0, 0)
	for a in A:
		at -= a
		df += c - a
		tmp = at * df
		if an < tmp:
			an = tmp
		else:
			break
	ans.append(an)
print(*ans, sep='\n')


(ans, c) = ([], 1000)
for _ in range(int(input())):
	N = int(input())
	A = sorted([int(x) for x in input().split()])
	at = sum(A)
	(df, an) = (0, 0)
	for a in A:
		at -= a
		df += c - a
		an = max(an, at * df)
	ans.append(an)
print(*ans, sep='\n')


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	arr = list(map(int, stdin.readline().split()))
	arr.sort(reverse=True)
	(i, above) = (1, arr[0])
	total = sum(arr)
	high = 0
	while i < n:
		if high < above * (1000 * (n - i) - total + above):
			high = above * (1000 * (n - i) - total + above)
		above += arr[i]
		i += 1
	print(high)


t = int(input())
for i in range(t):
	n = int(input())
	attack_lst = list(map(int, input().split()))
	attack_sum = 0
	defencce_sum = 0
	attack_lst.sort()
	if n == 2:
		print(attack_lst[0] * attack_lst[-1])
	else:
		fsum = [1000 - attack_lst[0]]
		bsum = [attack_lst[-1]]
		for j in range(1, n):
			fsum += [fsum[-1] + 1000 - attack_lst[j]]
		for j in range(n - 2, -1, -1):
			bsum += [bsum[-1] + attack_lst[j]]
		bsum = bsum[::-1]
		mx = 0
		for j in range(0, n - 1):
			temp = fsum[j] * bsum[j + 1]
			if temp > mx:
				mx = temp
		print(mx)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	(m, p, q) = (0, 0, 0)
	if n == 2:
		m = (1000 - arr[0]) * arr[1]
	else:
		for i in range(n - 1):
			p = p + (1000 - arr[i])
			q = 0
			for j in range(i + 1, n):
				q = q + arr[j]
			r = p * q
			m = max(m, r)
	print(m)


t = int(input())
for tt in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ap = []
	dp = []
	arr.sort()
	final_rating = 0
	s_dp = 0
	s_ap = 0
	if n == 2:
		dp.append(1000 - arr[0])
		ap.append(arr[1])
		final_rating = sum(ap) * sum(dp)
	else:
		for i in range(n - 1):
			s_dp = s_dp + (1000 - arr[i])
			s_ap = 0
			for j in range(i + 1, n):
				s_ap = s_ap + arr[j]
				new_rating = s_dp * s_ap
				if new_rating > final_rating:
					final_rating = new_rating
	print(final_rating)


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	attack = sum(a)
	res = 0
	defense = 0
	for i in range(len(a)):
		attack -= a[i]
		defense += 1000 - a[i]
		res = max(res, attack * defense)
	print(res)


T = int(input())
for _ in range(T):
	N = int(input())
	list_A = list(map(int, input().split(' ')))
	list_B = sorted(list_A)
	ans = 0
	for i in range(N - 1):
		defence = (i + 1) * 1000 - sum(list_B[0:i + 1])
		attack = sum(list_B[i + 1:])
		rating = attack * defence
		ans = max(ans, rating)
	print(ans)


inputNo = int(input())
for _ in range(inputNo):
	a = input()
	inp = input()
	inp = [int(x) for x in inp.split(' ')]
	inp.sort()
	attack = sum(inp)
	defense = 0
	highest = 0
	for i in inp:
		defense += 1000 - i
		attack -= i
		highest = max(highest, defense * attack)
	print(highest)


import math

def solve(arr, n):
	attackers = sum(arr)
	defenders = 0
	res = -math.inf
	for x in range(n):
		attackers -= arr[x]
		defenders += 1000 - arr[x]
		res = max(res, attackers * defenders)
	print(res)

def main():
	t = int(input())
	while t:
		n = int(input())
		arr = [int(x) for x in input().split(' ')]
		arr.sort()
		solve(arr, n)
		t -= 1
main()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	total_sum = sum(arr)
	part1 = 0
	res = 0
	for i in range(n - 1):
		part1 += arr[i]
		part2 = (n - i - 1) * 1000 - (total_sum - part1)
		res = max(res, part1 * part2)
	print(res)


try:
	T = int(input())
	while T:
		N = int(input())
		A = list(map(int, input().split()))
		A.sort(reverse=True)
		B = []
		for i in range(N):
			B.append(1000 - A[i])
		sumA = 0
		sumB = sum(B)
		ans = 0
		for i in range(N):
			sumA += A[i]
			sumB -= B[i]
			ans = max(ans, sumA * sumB)
		print(ans)
		T -= 1
except:
	pass


t = int(input())
while t:
	n = int(input())
	points = [int(x) for x in input().split()]
	points.sort(reverse=True)
	asum = 0
	prod = 0
	for i in range(n - 1):
		asum += points[i]
		dsum = 0
		for j in range(i + 1, n):
			dsum += 1000 - points[j]
		if prod < asum * dsum:
			prod = asum * dsum
	print(prod)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	a = 0
	d = 0
	m = 0
	p.sort(reverse=True)
	for i in range(n - 1):
		d = 0
		a += p[i]
		for j in range(i + 1, n):
			d += 1000 - p[j]
		if m < a * d:
			m = a * d
	print(m)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split(' ')))
	A.sort(reverse=True)
	Total = sum(A)
	attack = 0
	defense = 1000 * N - Total
	Ans = 0
	for i in range(len(A)):
		attack += A[i]
		defense -= 1000 - A[i]
		Ans = max(Ans, attack * defense)
	print(Ans)


for i in range(int(input())):
	soldiers = int(input())
	atk = list(map(int, input().split(' ')))
	mana = [0]
	for i in range(soldiers):
		weak = int(min(atk))
		firepower = sum(atk)
		shields = sum(mana)
		if firepower * shields < (1000 - weak + shields) * (firepower - weak):
			defender = 1000 - weak
			mana.append(defender)
			atk.remove(weak)
		else:
			solution = firepower * shields
			break
	print(solution)


for t in range(int(input())):
	n = int(input())
	arr = sorted(map(int, input().split()), reverse=True)
	tot = sum(arr)
	ans = 0
	curr = 0
	for i in range(n):
		curr += arr[i]
		deff = 1000 * (n - i - 1) - (tot - curr)
		ans = max(ans, curr * deff)
	print(ans)


for i in range(int(input())):
	n = int(input())
	powers = list(map(int, input().split()))[:n]
	powers.sort(reverse=True)
	total = sum(powers)
	attack = 0
	defence = 1000 * n - total
	ans = 0
	for i in range(len(powers)):
		attack += powers[i]
		defence -= 1000 - powers[i]
		ans = max(ans, attack * defence)
	print(ans)


test = int(input())
for _ in range(test):
	N = int(input())
	points = sorted(list(map(int, input().split())))
	points.reverse()
	ans = 0
	for i in range(1, N):
		ATTACK = points[:i]
		DEFENSE = [1000 - x for x in points[i:]]
		if ans < sum(ATTACK) * sum(DEFENSE):
			ans = sum(ATTACK) * sum(DEFENSE)
		else:
			break
	print(ans)


for i in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	A.sort(reverse=True)
	(ans, attack, defense) = (0, 0, 1000 * n - sum(A))
	for i in range(1, n):
		attack += A[i - 1]
		defense -= 1000 - A[i - 1]
		ans = max(ans, attack * defense)
	print(ans)


for _ in range(int(input())):
	N = int(input())
	A = sorted(list(map(int, input().split())))[::-1]
	(ans, left, right) = (0, 0, 1000 * N - sum(A))
	for i in range(N):
		left += A[i]
		right -= 1000 - A[i]
		ans = max(ans, left * right)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	c = 0
	a = 0
	d = 0
	l1.sort()
	l2 = []
	l3 = []
	for i in range(n):
		if l1[i] > 500:
			a = a + l1[i]
			l2.append(l1[i])
		elif l1[i] < 500:
			d = d + (1000 - l1[i])
			l3.append(l1[i])
		else:
			c = c + 1
	for i in range(c):
		if a < d:
			a = a + 500
		else:
			d = d + 500
	q = a * d
	if a > d:
		while a > d and len(l2) > 0:
			k = min(l2)
			i = l2.index(k)
			l2[i] = 1001
			a = a - k
			d = d + (1000 - k)
			if q > a * d:
				break
			else:
				q = a * d
	else:
		while a < d and len(l3) > 0:
			k = max(l3)
			i = l3.index(k)
			l3[i] = -1
			a = a + k
			d = d - (1000 - k)
			if q > a * d:
				break
			else:
				q = a * d
	print(q)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	l = sum(arr[:n - 1])
	r = 1000 - arr[n - 1]
	ans = l * r
	for i in range(n - 2, -1, -1):
		l -= arr[i]
		r += 1000 - arr[i]
		ans = max(ans, l * r)
	print(ans)


tc = int(input())
for i in range(tc):
	n = int(input())
	rating = list(map(int, input().split(' ')))
	attack = defense = 0
	for i in range(n):
		attack += rating[i]
	rating.sort()
	maxrate = 0
	for i in range(n):
		attack -= rating[i]
		defense += 1000 - rating[i]
		rate = attack * defense
		maxrate = max(rate, maxrate)
	print(maxrate)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	A = sorted(A)
	a = sum(A)
	b = 0
	rating = a * b
	for i in range(N):
		a -= A[i]
		b += 1000 - A[i]
		temp = a * b
		if temp > rating:
			rating = temp
		else:
			pass
	print(rating)


t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	l.sort(reverse=True)
	(attack, diffense) = (0, 0)
	totSum = sum(l)
	ans = 0
	for i in range(n):
		attack += l[i]
		defense = 1000 * (n - i - 1) - (totSum - attack)
		ans = max(ans, attack * defense)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr.sort(reverse=True)
	defence = 0
	attack = 0
	for i in arr:
		defence += 1000 - i
	ans = 0
	for i in arr:
		attack += i
		defence = defence - (1000 - i)
		ans = max(ans, attack * defence)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = sorted(list(map(int, input().split())))[::-1]
	(atta, defe, suma) = (0, 1000 * n - sum(a), 0)
	for j in range(n):
		atta += a[j]
		defe -= 1000 - a[j]
		suma = max(suma, atta * defe)
	print(suma)


t = int(input())
while t:
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort(reverse=True)
	tot = sum(a)
	s = 0
	maxRating = 0
	for i in range(n):
		maxRating = max(maxRating, s * (1000 * (n - i) - (tot - s)))
		s += a[i]
	print(maxRating)
	t -= 1


import numpy
T = int(input())
for j in range(T):
	n = int(input())
	points = []
	points = list(map(int, input().split()))
	a = sum(points)
	d = 0
	x = 0
	points.sort()
	for i in range(n):
		x = max(x, a * d)
		a -= points[i]
		d += 1000 - points[i]
	print(x)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	att = 0
	dff = 0
	mid = n // 2
	arr.sort()
	for i in range(mid):
		dff += 1000 - arr[i]
	for i in range(mid, n):
		att += arr[i]
	rat = att * dff
	at = att
	df = dff
	for i in range(mid, n):
		att -= arr[i]
		dff += 1000 - arr[i]
		temp = att * dff
		rat = max(rat, temp)
	att = at
	dff = df
	for i in range(mid - 1, -1, -1):
		dff -= 1000 - arr[i]
		att += arr[i]
		temp = att * dff
		rat = max(rat, temp)
	print(rat)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	A = sorted(A, reverse=True)
	Attack = []
	Defence = []
	update_Defence = []
	Rating = []
	for i in range(len(A)):
		for j in range(i + 1):
			Attack.append(A[j])
		for k in range(i + 1, len(A)):
			Defence.append(A[k])
		for i in range(len(Defence)):
			update_Defence.append(1000 - Defence[i])
		sum_Attack = sum(Attack)
		sum_Defence = sum(update_Defence)
		Rating.append(sum_Attack * sum_Defence)
		Attack.clear()
		Defence.clear()
		update_Defence.clear()
	print(max(Rating))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(a, d, x) = (sum(l), 0, 0)
	l.sort()
	for i in range(n):
		x = max(x, a * d)
		a -= l[i]
		d += 1000 - l[i]
	x = max(x, a * d)
	print(x)


for i in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())))[::-1]
	(ans, left, right) = (0, 0, 1000 * n - sum(a))
	for i in range(1, n):
		left += a[i - 1]
		right -= 1000 - a[i - 1]
		ans = max(ans, left * right)
	print(ans)


for t in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	sm = sum(arr)
	curr = 0
	ans = 0
	arr.sort(reverse=True)
	for i in range(n):
		ans = max(ans, curr * (1000 * (n - i) - sm + curr))
		curr += arr[i]
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	l = sum(a[1:n])
	r = 1000 - a[0]
	ans = l * r
	for i in range(1, n):
		l -= a[i]
		r += 1000 - a[i]
		ans = max(ans, l * r)
	print(ans)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	temp = []
	l = sorted(l, reverse=True)
	for i in range(n):
		t1 = l[:i]
		t2 = l[i:]
		attack = sum(t1)
		defense = 1000 * len(t2) - sum(t2)
		rating = attack * defense
		temp.append(rating)
	print(max(temp))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	atk = sum(a)
	dfn = 0
	rating = []
	for i in a:
		dfn += 1000 - i
		atk -= i
		rating.append(atk * dfn)
	print(max(rating))


from collections import Counter, defaultdict
from sys import stdin, stdout, setrecursionlimit
from heapq import nlargest, nsmallest
import math
setrecursionlimit(2147400000)

def outnl(x):
	stdout.write(str(x) + '\n')

def outsl(x):
	stdout.write(str(x) + ' ')

def instr():
	return stdin.readline().strip()

def inint():
	return int(stdin.readline())

def inspsint():
	return map(int, stdin.readline().strip().split())

def inlist():
	return list(map(int, stdin.readline().strip().split()))
for _ in range(inint()):
	n = inint()
	l = inlist()
	l.sort()
	attack = sum(l)
	defence = 0
	ans = -float('inf')
	for i in l:
		defence += 1000 - i
		attack -= i
		ans = max(defence * attack, ans)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	attrat = sum(a)
	defrat = 0
	temp = 0
	for i in range(n):
		attrat -= a[i]
		defrat += 1000 - a[i]
		temp = max(temp, attrat * defrat)
	print(temp)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort(reverse=True)
	prod = []
	for i in range(n - 1):
		sumA = 0
		sumD = 0
		for j in range(n):
			if j <= i:
				sumA += a[j]
			else:
				sumD += 1000 - a[j]
		prod.append(sumA * sumD)
	print(max(prod))


T = int(input(''))
for _ in range(T):
	length = int(input(''))
	A = list(map(int, input('').split(' ')))
	A.sort()
	points = 0
	for mini in range(1, length):
		attack = sum(A[mini:])
		defense = sum(A[:mini])
		defense = 1000 * mini - defense
		point = defense * attack
		points = max(points, point)
	print(points)


T = int(input())
for _ in range(T):
	n = int(input())
	arr = [int(item) for item in input().split()]
	arr.sort(reverse=True)
	max1 = []
	for i in range(n):
		max1.append(sum(arr[:i]) * (1000 * (n - i) - sum(arr[i:])))
	print(max(max1))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	ans = []
	for i in range(n):
		ans.append(sum(arr[:i]) * (1000 * (n - i) - sum(arr[i:])))
	print(max(ans))


def sumSplit(left, right=[], difference=0):
	(sumLeft, sumRight) = (sum(left), sum(right))
	if sumLeft < sumRight or len(left) < len(right):
		return
	if sumLeft - sumRight == difference:
		return (left, right, difference)
	for (i, value) in enumerate(left):
		solution = sumSplit(left[:i] + left[i + 1:], right + [value], difference)
		if solution:
			return solution
	if right or difference > 0:
		return
	for targetDiff in range(1, sumLeft - min(left) + 1):
		solution = sumSplit(left, right, targetDiff)
		if solution:
			return solution
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort(reverse=True)
	ans = []
	for i in range(n):
		suma = sum(arr[:i])
		sumd = 1000 * (n - i) - sum(arr[i:])
		ans.append(suma * sumd)
	print(max(ans))


for _ in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	ls.sort()
	attack = sum(ls)
	defense = 0
	ans = attack * defense
	for i in ls:
		attack -= i
		defense += 1000 - i
		ans = max(ans, attack * defense)
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	ans = 0
	left = 0
	right = 1000 * n - sum(a)
	for i in range(1, n):
		left += a[i - 1]
		right -= 1000 - a[i - 1]
		ans = max(ans, left * right)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	x.sort(reverse=True)
	max1 = 0
	suma = 0
	sumb = 1000 * n - sum(x)
	for j in range(1, len(x)):
		suma += x[j - 1]
		sumb -= 1000 - x[j - 1]
		max1 = max(max1, suma * sumb)
	print(max1)


import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

def il():
	return [int(a) for a in input().strip().split()]

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

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7

def maxpro(arr, n):
	arr.sort(reverse=True)
	att = 0
	de = 1000 - arr[-1]
	for k in range(n - 1):
		att += arr[k]
	i = n - 2
	ans = -float('inf')
	ans = max(ans, de * att)
	while i > 0:
		att -= arr[i]
		de += 1000 - arr[i]
		i -= 1
		ans = max(ans, att * de)
	print(ans)
for _ in range(ii()):
	n = ii()
	arr = il()
	maxpro(arr, n)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	s = sum(a)
	p = 0
	m = 0
	for i in a:
		s -= i
		p += 1000 - i
		m = max(m, s * p)
	print(m)


for _ in range(0, int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	ans = 0
	total = sum(a)
	leftSum = 0
	for i in range(n):
		ans = max(ans, leftSum * (1000 * (n - i) - (total - leftSum)))
		leftSum += a[i]
	print(ans)


for i in range(int(input())):
	n = int(input())
	s = list(map(int, input().split(' ')))
	s.sort(reverse=True)
	(ans, left, right) = (0, 0, 1000 * n - sum(s))
	for i in range(n):
		left += s[i]
		right -= 1000 - s[i]
		ans = max(ans, left * right)
	print(ans)


def sum_up(attckers_list1):
	total = 0
	for item in attckers_list1:
		total = total + item
	return total
for _ in range(int(input())):
	n = int(input())
	attackers_list = list(map(int, input().split()))
	attackers_list.sort()
	att_val = sum_up(attackers_list)
	deff_val = 0
	old_max = att_val * deff_val
	for i in range(n):
		att = attackers_list[i]
		deff = 1000 - att
		att_val = att_val - att
		deff_val = deff_val + deff
		new_max = att_val * deff_val
		if new_max > old_max:
			old_max = new_max
		else:
			break
	print(old_max)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	pr1 = [0] * n
	pr1[0] = 1000 - arr[0]
	for i in range(1, n):
		pr1[i] = pr1[i - 1] + (1000 - arr[i])
	pr2 = [0] * n
	pr2[n - 1] = arr[n - 1]
	for i in range(n - 2, -1, -1):
		pr2[i] = pr2[i + 1] + arr[i]
	mx = float('-inf')
	for i in range(1, n):
		mx = max(mx, pr1[i - 1] * pr2[i])
	print(mx)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	a = sorted(a)
	attack = sum(a)
	defence = 0
	temp = []
	for i in a:
		defence += 1000 - i
		attack = attack - i
		temp.append(defence * attack)
	print(max(temp))


t = int(input())
while t:
	n = int(input())
	army = list(map(int, input().split()))
	army.sort()
	maxRating = 0
	for i in range(0, n - 1):
		maxRating = max((1000 * (i + 1) - sum(army[0:i + 1])) * sum(army[i + 1:n]), maxRating)
	print(maxRating)
	t -= 1


import sys
from itertools import count, islice
for s in islice(sys.stdin, 2, None, 2):
	a = sorted(map(int, s.split()))
	for i in range(1, len(a)):
		a[i] += a[i - 1]
	print(max(((i - x) * (a[-1] - x) for (i, x) in zip(count(1000, 1000), a))))


strng = lambda : input().split()[0]
inp = lambda : int(input())
mul = lambda : map(int, input().split())
jn = lambda x, l: x.join(map(str, l))
slst = lambda : list(input().split()[0])
silst = lambda : list(map(int, input().split()[0]))
lst = lambda : list(map(int, input().split()))
dd = lambda : defaultdict(lambda : 0)
import sys
input = sys.stdin.readline
from heapq import heapify, nsmallest, nlargest, heappush, heappop
from collections import defaultdict, deque
from math import ceil, log, floor, sqrt, gcd, log10
for _ in range(inp()):
	n = inp()
	a = lst()
	at = [0] * n
	dt = [0] * n
	a.sort()
	cat = 0
	dat = 0
	for i in range(n):
		cat += a[n - i - 1]
		at[n - i - 1] = cat
		dat += 1000 - a[i]
		dt[i] = dat
	ans = 0
	for i in range(n - 1):
		ans = max(ans, dt[i] * at[i + 1])
	print(ans)


def solution():
	n = int(input())
	A = list(map(int, input().split()))
	A.sort(reverse=True)
	maxTotal = 0
	apTotal = 0
	for i in range(len(A)):
		apTotal += A[i]
		dpTotal = 0
		for j in range(i + 1, len(A)):
			dpTotal += 1000 - A[j]
		totalPoint = apTotal * dpTotal
		maxTotal = totalPoint if totalPoint > maxTotal else maxTotal
	print(maxTotal)
t = int(input())
while t > 0:
	solution()
	t -= 1


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	arr.sort()
	s = sum(arr)
	ans = 0
	x = 0
	for i in range(n):
		x += arr[i]
		req = ((i + 1) * 1000 - x) * (s - x)
		if req > ans:
			ans = req
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort(reverse=True)
	attack = rating = 0
	defense = 1000 * n - sum(a)
	for i in a:
		attack += i
		defense -= 1000 - i
		rating = max(rating, attack * defense)
	print(rating)