Let f be a function, such that, for an array A of size M, f(A) is defined as

f(A) = \sum_{i=1}^{M}\sum_{j=1, j \ne i}^{j=M} (A_{i}\cdot A_{j})

You are given an array C of size N. In one operation on the array, you can:
Choose an index i (1≤ i ≤ |C|)
Select two positive integers X and Y such that X+Y = C_{i}
Remove the element C_{i} from the array C
Insert the elements X and Y to the array C

Find the maximum value of f(C) that can be obtained using any (possibly zero) number of given operations. Since this value can be huge, output the answer modulo 998244353.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains an integer N, denoting the size of the array.
- The next line contains N space-separated integers C_{1}, C_{2}, \ldots, C_{N}, the elements of the array C.

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

For each test case, output on a new line, the maximum value of f(C) that can be obtained using any (possibly zero) number of given operations. Since this value can be huge, output the answer modulo 998244353.

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

$1 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 2\cdot 10^{5}$
$1 ≤ C_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases won't exceed $2\cdot 10^{5}$.

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

----- Sample Output 1 ------ 
6
12

----- explanation 1 ------ 
Test case $1$: Using one operation, we choose $i = 2$, set $X = 1$ and $Y = 1$, remove $2$ from the array, and insert $X$ and $Y$. Thus, the final array is $C = [1, 1, 1]$.  
Here, $f(C) = (A_{1}\cdot A_{2}) + (A_{1}\cdot A_{3}) + (A_{2}\cdot A_{1}) + (A_{2}\cdot A_{3}) + (A_{3}\cdot A_{1}) + (A_{3}\cdot A_{2}) = 1+1+1+1+1+1 = 6$. 

Test case $2$:
- Operation $1$: We choose $i = 2$, set $X = 1$ and $Y = 2$, remove $3$ from the array, and insert $X$ and $Y$. Thus, the final array is $C = [1, 1, 2]$.  
- Operation $2$: We choose $i = 3$, set $X = 1$ and $Y = 1$, remove $3$ from the array, and insert $X$ and $Y$. Thus, the final array is $C = [1, 1, 1, 1]$. 

Here, $f(C) = 12$.

Difficulty: EASY
Tags: Mathematics

Starter code:

Solutions:
for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = 0
	for i in range(n):
		s = s + l[i]
		s = s % 998244353
	s = s * (s - 1)
	s = s % 998244353
	print(s)


for testcases in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	(sum, mod) = (0, 998244353)
	for i in a:
		sum += i
		sum %= mod
	print(sum * (sum - 1) % mod)


mod = 998244353
for _ in range(int(input())):
	n = input()
	a = sum([int(x) for x in input().split()])
	print(a * (a - 1) % mod)


t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	s = sum(l)
	print(s * (s - 1) % 998244353)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(sum(a) * (sum(a) - 1) % 998244353)


for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	(s, m) = (0, 998244353)
	for i in c:
		s += i
		s %= m
	print(s * (s - 1) % m)


base = 998244353
for _ in range(int(input())):
	N = int(input())
	A = sum(map(int, input().split()))
	print(A % base * ((A - 1) % base) % base)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	print(s * (s - 1) % 998244353)
for _ in range(int(input())):
	solve()


for i in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	s = sum(c)
	print(s * (s - 1) % 998244353)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	r = sum(l)
	r = r * (r - 1)
	print(r % 998244353)


t = int(input())
while t != 0:
	n = int(input())
	l = list(map(int, input().split()))
	r = sum(l)
	r = r * (r - 1)
	print(r % 998244353)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	r = sum(a) * (sum(a) - 1) % 998244353
	print(r % 998244353)


for t in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))
	s = sum(m)
	r = s * (s - 1) % 998244353
	print(r % 998244353)


T = int(input())
for _ in range(T):
	input()
	M = sum(list(map(int, input().split(' '))))
	print(M * (M - 1) % 998244353)


for _ in range(int(input())):
	le = int(input())
	l = [int(i) for i in input().split()]
	s = sum(l)
	tot = s % 998244353 * ((s - 1) % 998244353)
	print(tot % 998244353)


import math

def per(n, r):
	a = n * (n - 1) % 998244353
	return a
T = int(input())
for i in range(0, T):
	n = int(input())
	c = list(map(int, input().split()))
	sm = 0
	for i in range(0, n):
		sm += c[i]
	print(per(sm, 2))


NN = 998244353
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	x = sum(arr)
	ans = x % NN * (x - 1) % NN % NN
	print(ans % NN)


T = int(input())
for t in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	sum = 0
	for x in arr:
		sum += x
	mod = 998244353
	ans = sum * (sum - 1) % mod
	print(ans)


for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	n = sum(c)
	print(n * (n - 1) % 998244353)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	suml = sum(l)
	print(suml * (suml - 1) % 998244353)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	k = sum(a)
	print(k * (k - 1) % 998244353)


mod = 998244353
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print((sum(a) * sum(a) - sum(a)) % mod)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	val = 0
	val = sum(a)
	ans = val * (val - 1) % 998244353
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = n
	for i in a:
		if i != 1:
			s += i - 1
	print(s * (s - 1) % 998244353)


for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	s = sum(c)
	print((s ** 2 - s) % 998244353)


tc = int(input())
for t in range(tc):
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	print(s * (s - 1) % 998244353)


t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	a = list(map(int, input().split()))
	m = 0
	for i in a:
		m = m + i
	print(m * (m - 1) % 998244353)


for item in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print((sum(l) - 1) * sum(l) % 998244353)


x = int(input())
for i in range(x):
	f = 0
	ind = int(input())
	lst = list(map(int, input().split()))
	s = sum(lst)
	f = s * (s - 1)
	print(f % 998244353)


MOD = 998244353
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	res = 0
	for i in arr:
		res = (res + i) % MOD
	print(res * (res - 1) % MOD)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	t = sum(a)
	m = t ** 2 - t
	print(m % 998244353)


t = int(input())
for _ in range(t):
	n = int(input())
	array = list(map(int, input().split()))
	nf = sum(array)
	fsum = nf ** 2 - nf
	print(fsum % 998244353)


t = int(input())
for i in range(0, t):
	s = int(input())
	x = list(map(int, input().split(' ', s)))
	count = 0
	for i in x:
		count = count + i
	sum = count * (count - 1)
	print(sum % 998244353)


for i in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))
	higest_value = sum(m)
	t = higest_value * (higest_value - 1)
	print(t % 998244353)


for i in range(int(input())):
	size = int(input())
	result = []
	ele = [int(i) for i in input().split(' ')]
	s = sum(ele)
	print(s * (s - 1) % 998244353)


for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	s = sum(c)
	k = 1
	if n == 1 and s == 1:
		print(k)
	else:
		print(s * (s - 1) % 998244353)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	x = s * (s - 1) % 998244353
	if s == 1:
		print(1)
	else:
		print(x)


t = int(input())
while t > 0:
	n = int(input())
	li = [int(i) for i in input().split()]
	maxi = sum(li)
	maxnum = maxi * (maxi - 1)
	print(maxnum % 998244353)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	b = sum(c)
	a = b * b - b
	print(a % 998244353)


t = int(input())
a = []
for i in range(t):
	input()
	a.append(list(map(int, input().split())))
for i in range(t):
	count = sum(a[i])
	count = (count - 1) * count
	print(count % 998244353)


n = int(input())
for _ in range(n):
	a = int(input())
	h = list(map(int, input().split()))
	l = sum(h)
	print((l - 1) * l % 998244353)


t = int(input())
for i in range(t):
	k = int(input())
	h = list(map(int, input().split()))
	l = sum(h)
	l = l * (l - 1)
	print(l % 998244353)


for _ in range(int(input())):
	n = int(input())
	c = [int(i) for i in input().split()]
	x = 0
	i = 0
	while i < len(c):
		if c[i] > 1:
			x += c[i]
		else:
			x += 1
		i += 1
	ans = 1 * (x - 1) * x
	print(ans % 998244353)


def solve(arr, n):
	tot = sum(arr)
	return tot * (tot - 1) % 998244353
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(arr, n))


import math
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	print(math.perm(s, 2) % 998244353)


import sys

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

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

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

def get_print(x):
	sys.stdout.write(x + '\n')

def get_print_int_same(x):
	sys.stdout.write(str(x) + ' ')

def get_print_same(x):
	sys.stdout.write(x + ' ')
from sys import maxsize
MOD = 998244353

def solve():
	for _ in range(get_int()):
		n = get_int()
		arr = get_list()
		summ = sum(arr)
		get_print_int(summ * (summ - 1) % MOD)
solve()


def highestnumber(l):
	summ = sum(l)
	return (summ - 1) * summ % 998244353
for _ in range(int(input())):
	n = int(input())
	print(highestnumber(list(map(int, input().split()))))


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	j = max(l)
	print((sum(l) - 1) * sum(l) % 998244353)


T = int(input())
for i in range(T):
	N = int(input())
	l = list(map(int, input().split()))
	b = sum(l)
	print(b * (b - 1) % 998244353)


for i in range(int(input())):
	a = int(input())
	lis = list(map(int, input().split()))
	p = 0
	for i in range(a):
		p = (p + lis[i]) % 998244353
	p = p * (p - 1) % 998244353
	print(p)


goals = int(input())
for distractions in range(goals):
	aim = int(input())
	life = list(map(int, input().split()))
	wife = 0
	for j in range(aim):
		wife = (wife + life[j]) % 998244353
	wife = wife * (wife - 1) % 998244353
	print(wife)


mod = 998244353
for _ in range(int(input())):
	n = int(input())
	s = [int(j) for j in input().split()]
	res = sum(s)
	res = res ** 2 - res
	print(res % mod)


T = int(input())
for i in range(T):
	n = int(input())
	c = [int(i) for i in input().split()]
	s = sum(c)
	print((s * s - s) % 998244353)


t = int(input())
while t:
	n = int(input())
	C = list(map(int, input().split()))
	count = sum(C)
	M = 998244353
	re = count % M * ((count - 1) % M) % M
	print(re)
	t -= 1


from collections import Counter, UserString
mod = lambda n, v=10 ** 9 + 7: n % v
fc_ = [1]
for i in range(1, 1000001):
	fc_.append(i * fc_[i - 1])
	fc_[i] = mod(fc_[i])

def fact(n):
	return fc_[n]

def printm(n, v=10 ** 9 + 7):
	print(mod(n, v))

def yn(b, caps=False):
	if b:
		returning = 'Yes'
	else:
		returning = 'No'
	if caps:
		return returning.upper()
	return returning

def isPrime(n):
	if n > 1:
		for i in range(2, int(n ** 0.5) + 1):
			if not n % i:
				return False
		else:
			return True
	return True

def decimal(n):
	return int(ans) + int(int(ans) != ans)

class mutableStr(UserString):

	def ins(self, n, s):
		if n < 0:
			self.data = self.data = ''.join(list(self.data)[:n + 1]) + s + ''.join(list(self.data)[n + 1:])
		else:
			self.data = ''.join(list(self.data)[:n]) + s + ''.join(list(self.data)[n:])

	def rem(self, s):
		self.data = self.data.replace(s, '')
alphabetOrd = [97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122]
alphabet = list('abcdefghijklmnopqrstuvwxyz')
r2 = lambda n: range(1, n + 1)
alph = lambda s: s.isalpha()
sl = lambda l: list(set(l))
inf = float('inf')
soi = lambda : sorted(input())
ii = lambda : int(input())
li = lambda : list(map(int, input().split()))
si = lambda : mutableStr(input())
lsi = lambda : list(input())
sepi = lambda : map(int, input().split())
seti = lambda : set(map(int, input().split()))
for t in range(int(input())):
	lenOfLst = ii()
	lst = li()
	lstSum = sum(lst)
	ans = lstSum ** 2 - lstSum
	printm(ans, 998244353)


n = int(input())
for i in range(n):
	a = int(input())
	m = 998244353
	l = list(map(int, input().split()))
	k = sum(l)
	d = k * (k - 1)
	print(d % m)


t = int(input())
while t:
	n = int(input())
	c = list(map(int, input().split()))
	Sum = sum(c)
	ans = Sum * (Sum - 1)
	print(ans % 998244353)
	t -= 1


p = int(input())
for i in range(p):
	b = int(input())
	lis = list(map(int, input().split()))
	tot = sum(lis)
	c = tot * (tot - 1)
	print(c % 998244353)


M = 998244353
t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split(' ')))
	s = 0
	for x in a:
		s = (s + x) % M
	print((s - 1) * s % M)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	C = list(map(int, input().split()))
	s = sum(C)
	print(s * (s - 1) % 998244353)


import math
for tc in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	print(math.perm(sum(c), 2) % 998244353)


T = int(input())
for i in range(T):
	N = int(input())
	C = list(map(int, input().strip().split()))
	s = sum(C)
	print(s * (s - 1) % 998244353)


for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	res = sum(lis)
	res = res * (res - 1)
	print(res % 998244353)


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().strip().split()))
	ans = sum(l)
	ans = ans * (ans - 1)
	print(ans % 998244353)
	t -= 1


for _ in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	s = sum(l) * (sum(l) - 1)
	print(s % 998244353)