Joey is low on money. His friend Chandler wants to lend Joey some money, but can't give him directly, as Joey is too proud of himself to accept it. So, in order to trick him, Chandler asks Joey to play a game.

In this game, Chandler gives Joey an array $a_1, a_2, \dots, a_n$ ($n \geq 2$) of positive integers ($a_i \ge 1$).

Joey can perform the following operation on the array any number of times:

Take two indices $i$ and $j$ ($1 \le i < j \le n)$.

Choose two integers $x$ and $y$ ($x, y \ge 1$) such that $x \cdot y = a_i \cdot a_j$.

Replace $a_i$ by $x$ and $a_j$ by $y$.

In the end, Joey will get the money equal to the sum of elements of the final array.

Find the maximum amount of money $\mathrm{ans}$ Joey can get but print $2022 \cdot \mathrm{ans}$. Why multiplied by $2022$? Because we are never gonna see it again!

It is guaranteed that the product of all the elements of the array $a$ doesn't exceed $10^{12}$.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 4000$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \leq n \leq 50$) — the length of the array $a$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^6$) — the array itself.

It's guaranteed that the product of all $a_i$ doesn't exceed $10^{12}$ (i. e. $a_1 \cdot a_2 \cdot \ldots \cdot a_n \le 10^{12}$).


-----Output-----

For each test case, print the maximum money Joey can get multiplied by $2022$.


-----Examples-----

Input
3
3
2 3 2
2
1 3
3
1000000 1000000 1
Output
28308
8088
2022000000004044


-----Note-----

In the first test case, Joey can do the following:

He chooses $i = 1$ and $j = 2$ (so he has $a[i] \cdot a[j] = 6$), chooses $x = 6$ and $y = 1$ and makes $a[i] = 6$ and $a[j] = 1$. $$[2, 3, 2] \xrightarrow[x = 6,\; y = 1]{i = 1,\; j = 2} [6, 1, 2]$$

He chooses $i = 1$ and $j = 3$ (so he has $a[i] \cdot a[j] = 12$), chooses $x = 12$ and $y = 1$ and makes $a[i] = 12$ and $a[j] = 1$. $$[6, 1, 2] \xrightarrow[x = 12,\; y = 1]{i = 1,\; j = 3} [12, 1, 1]$$

The sum is $14$ which is the maximum of all possible sums. The answer is $2022 \cdot 14 = 28308$.

Source: codeforces | Difficulty: EASY
Tags: Mathematics

Greedy algorithms


Solutions:
import sys
from itertools import permutations
from collections import Counter
import math
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	p = math.prod(a)
	print((p + len(a) - 1) * 2022)


p = int(input())
_ = 0
origin = []
while _ < p:
	q = input()
	z = list(map(int, input().split()))
	z.sort(reverse=True)
	origin.append(z)
	_ += 1

def h(i):
	ans = i[0]
	for t in i[1:]:
		if t != 1:
			ans *= t
		else:
			break
	ans = ans + len(i) - 1
	print(str(ans * 2022))
for i in origin:
	if i[0] != 1:
		h(i)
	else:
		print(str(sum(i) * 2022))


import sys

def main():
	n = int(input())
	to_print = []
	for _ in range(n):
		m = int(input())
		array = list(map(int, sys.stdin.readline().split()))
		max_sum = 1
		for element in array:
			max_sum *= element
		to_print.append(str((max_sum + m - 1) * 2022))
	sys.stdout.write('\n'.join(to_print))
main()


import sys
import math

def sol(n, a):
	a1 = math.prod(a) + (n - 1)
	return a1 * 2022
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	sys.stdout.write(str(sol(n, a)) + '\n')


import sys

def fn(a, l):
	x = 1
	for item in a:
		x *= item
	return x + l - 1
input = sys.stdin.readlines()
for i in range(int(input[0].strip('\n'))):
	l = int(input[2 * i + 1].strip('\n'))
	a = [int(x) for x in input[2 * i + 2].strip('\n').split(' ')]
	out = fn(a, l)
	print(2022 * out)


import sys
input = sys.stdin.readline
inp = sys.stdin.readline

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

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

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

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

def solve():
	n = ii()
	arr = li()
	arr.sort()
	curr = 1
	for i in arr:
		curr *= i
	res = curr + n - 1
	print(2022 * res)

def main():
	for _ in range(ii()):
		solve()
main()


import sys
readline = sys.stdin.readline
T = int(readline())
for _ in range(T):
	N = int(readline())
	numbers = list(map(int, readline().split()))
	answer = 1
	for number in numbers:
		answer *= number
	answer += N - 1
	answer *= 2022
	print(answer)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	lenOfArray = int(input())
	arr = list(map(int, input().split()))
	pi = 1
	for ele in arr:
		pi *= ele
	print(2022 * (pi + lenOfArray - 1))


import math

def main():
	testCases = int(input())
	for i in range(1, testCases + 1):
		arrayLength = int(input())
		array = input().split()
		temp = 1
		for x in array:
			temp *= int(x)
		result = (temp + arrayLength - 1) * 2022
		print(result)
main()


import sys
input = sys.stdin.readline

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

def readInt():
	return int(input())

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

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

def solve():
	n = readInt()
	arr = readList()
	v = 1
	for i in range(n):
		v *= arr[i]
	return (v + (n - 1)) * 2022
for _ in range(int(input())):
	print(solve())


import math as m
for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	prod = m.prod(a)
	prod = prod + (n - 1)
	print(prod * 2022)


import sys

def parse():
	t = int(sys.stdin.readline())
	for i in range(t):
		n = int(sys.stdin.readline())
		input_str = sys.stdin.readline().split()
		a = list(map(int, input_str))
		t = a[0] * a[1]
		summ = 1
		for j in range(2, n):
			t *= a[j]
			summ += 1
		summ += t
		print(2022 * summ)
parse()


import heapq
import sys
import math
import itertools
import os
input = lambda : sys.stdin.readline().strip()

def solve():
	n = int(input())
	l = [int(i) for i in input().split()]
	tot = 1
	for i in l:
		tot *= i
	print((tot + n - 1) * 2022)
for i in range(int(input())):
	solve()


import math
n = int(input())
for i in range(n):
	m = int(input())
	a = list(map(int, input().split()))
	print((math.prod(a) + m - 1) * 2022)


def multiply(lst):
	res = 1
	for i in lst:
		res *= i
	return res
for _ in range(int(input())):
	n = int(input())
	print(2022 * (multiply(map(int, input().split())) + n - 1))


import functools
kolvo_raz = input()
sa = []
for i in range(int(kolvo_raz)):
	a = input()
	b = input()
	kb = []
	qa = list(map(int, a.split()))
	qb = list(map(int, b.split()))
	kb = functools.reduce(lambda x, y: x * y, qb)
	sa.append(2022 * (kb + qa[0] - 1))
for i in range(0, int(kolvo_raz), 1):
	print(sa[i])


for _ in [0] * int(input()):
	print(2022 * (int(input()) - 1 + __import__('math').prod(map(int, input().split()))))


from math import prod
for _ in range(int(input())):
	n = int(input()) - 1
	print((prod(map(int, input().split())) + n) * 2022)


def sol():
	n = int(input())
	for i in range(n):
		m = int(input())
		l = list(map(int, input().split(' ')))
		o = 1
		for j in l:
			o = o * j
		o = o + m - 1
		print(o * 2022)
sol()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	l = int(input())
	ans = 1
	a = [int(i) for i in input().split()]
	for i in a:
		ans *= i
	print((ans + l - 1) * 2022)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	m = 1
	for v in arr:
		m *= v
	m += n - 1
	print(2022 * m)


def f(L):
	n = len(L)
	ans = 1
	for i in L:
		ans *= i
	return (ans + n - 1) * 2022
n = int(input())
for i in range(n):
	x = int(input())
	L = list(map(int, input().split()))
	print(f(L))


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	arr = sys.stdin.readline().split()
	arr = [int(i) for i in arr]
	ans = 1
	for i in arr:
		ans *= i
	ans += n - 1
	print(ans * 2022)


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	prod = 1
	for i in a:
		prod *= i
	print((prod + n - 1) * 2022)


n = int(input())
for _ in range(n):
	m = int(input())
	arr = list(map(int, input().split()))
	ans = 1
	for i in arr:
		ans *= i
	ans += m - 1
	ans *= 2022
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	tich = 1
	for i in a:
		tich = tich * i
	print((tich + n - 1) * 2022)


def fun(l, n):
	ans = 1
	for i in range(n):
		ans = ans * l[i]
	ans = ans + n - 1
	print(ans * 2022)
t = int(input())
for j in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	fun(l, n)


def multiplyList(myList):
	result = 1
	for x in myList:
		result = result * x
	return result
a = int(input())
while a > 0:
	b = int(input())
	nums = map(int, input().split())
	print(2022 * (multiplyList(nums) + (b - 1)))
	a = a - 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	prod = 1
	for e in a:
		prod *= e
	ans = prod + n - 1
	print(ans * 2022)


result = []
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	res = 1
	for j in arr:
		res *= j
	res += n - 1
	result.append(2022 * res)
for i in result:
	print(i)


import sys
input = sys.stdin.readline

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

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
num_test = inp()
for test_idx in range(num_test):
	n = inp()
	arr = inlt()
	mul = 1
	for a in arr:
		mul *= a
	ans = 2022 * (mul + (n - 1))
	print(ans)


t = int(input())
while t:
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = 1
	for i in a:
		ans *= i
	ans += n - 1
	print(ans * 2022)
	t -= 1


def exe():
	m = 1
	for i in lst:
		m = m * i
	s = n - 1
	return (m + s) * 2022
for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	print(exe())


def sol(arr, n):
	p = 1
	for i in range(n):
		p *= arr[i]
	p += n - 1
	return p * 2022
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(sol(arr, n))


def money(listno):
	array = listno.split()
	for i in range(len(array)):
		array[i] = int(array[i])
	ans = 1
	for x in array:
		ans *= x
	return (ans + len(array) - 1) * 2022
for i in range(int(input())):
	input()
	print(money(input()))


def multip(AA):
	result = 1
	for x in AA:
		result = result * x
	return result

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	s = multip(a)
	print(2022 * (s + n - 1))
TTT = int(input())
while TTT:
	solve()
	TTT -= 1


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	a.sort()
	p = math.prod(a)
	print((p + n - 1) * 2022)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	p = 1
	for i in l:
		p *= i
	print((p + n - 1) * 2022)


t = int(input())
while t:
	t -= 1
	n = int(input())
	j = 1
	l = list(map(int, input().split()))
	for i in l:
		j *= i
	j += n - 1
	print(j * 2022)


outputs = []
for i in range(int(input())):
	input()
	res = 1
	l = input().split()
	for a in l:
		res *= int(a)
	outputs.append(res + len(l) - 1)
for o in outputs:
	print(2022 * o)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	ans = 1
	for x in a:
		ans *= x
	ans += n - 1
	return 2022 * ans
t = int(input())
for _ in range(t):
	print(solve())


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	pro = 1
	for j in arr:
		pro *= j
	pro += n - 1
	print(pro * 2022)


def fun(x1):
	ans = 1
	for i in range(len(x1)):
		ans = ans * x1[i]
	return ans
t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	list1 = list(map(int, input().strip().split()))
	product = fun(list1)
	print(2022 * (product + n - 1))


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


for _ in range(int(input())):

	def p(l):
		a = 1
		for i in l:
			a = a * i
		return a
	n = int(input())
	arr = list(map(int, input().split(' ')))
	print((p(arr) + (len(arr) - 1)) * 2022)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	prod = 1
	for x in a:
		prod *= x
	print((prod + n - 1) * 2022)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print((len(a) - 1 + math.prod(a)) * 2022)


def solver():
	n = int(input())
	ans = 1
	x = map(int, input().split())
	for i in x:
		ans = ans * i
	ans = ans + n - 1
	print(ans * 2022)
for i in range(int(input())):
	solver()


for i in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	ans = 1
	for i in lis:
		ans *= i
	print(2022 * (ans + n - 1))


import math
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	r = math.prod(l)
	print(2022 * (r + n - 1))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 1
	for i in a:
		ans *= i
	ans += n - 1
	print(2022 * ans)


t = int(input())
m = 1
op = []
while m <= t:
	n = int(input())
	st = input()
	lst = [int(x) for x in st.split(' ')]
	sum = 1
	for i in range(n):
		sum *= lst[i]
	result = 2022 * (sum + (len(lst) - 1))
	op.append(result)
	m += 1
for i in op:
	print(i)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	res = 1
	for ele in arr:
		res *= ele
	mod = 10 ** 9 + 7
	ans = 2022 * (res + n - 1)
	print(ans)


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


test = int(input())
for i in range(test):
	elements = int(input())
	result = 1
	liste = list(map(int, input().split(' ')))
	for el in liste:
		result = result * el
	print((result + len(liste) - 1) * 2022)


from math import prod
tests = int(input())
for _ in range(tests):
	n = int(input())
	nums = list(map(int, input().split()))
	print((prod(nums) + n - 1) * 2022)


import functools as ft
import itertools as it
import operator
for _ in range(int(input())):
	n = int(input())
	a = ft.reduce(operator.mul, map(int, input().split()))
	print((a + n - 1) * 2022)


def main():
	solution()

def solution():
	t = int(input())
	for i in range(t):
		n = int(input())
		nums = [int(num) for num in input().split(' ')]
		if n == 1:
			print(nums[0])
			continue
		prod = 1
		for num in nums:
			prod *= num
		print((prod + len(nums) - 1) * 2022)
main()


t = int(input())
for _ in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	ans = 1
	for num in nums:
		ans *= num
	ans += len(nums) - 1
	print(ans * 2022)


import math
joey_takes_money = lambda arr, n: 2022 * (math.prod(arr) + n - 1)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(joey_takes_money(arr, n))


import math
T = int(input(''))
for i in range(T):
	n = int(input())
	str1 = input()
	l1 = [int(c) for c in str1.split()]
	prod = 1
	for element in l1:
		prod *= element
	ans = (prod + n - 1) * 2022
	print(ans)


import operator, functools
for t in range(int(input())):
	n = int(input())
	print(2022 * (functools.reduce(operator.mul, map(int, input().split())) + n - 1))


def A(arr):
	n = len(arr)
	res = 1
	for i in arr:
		res *= i
	return (res + n - 1) * 2022
for i in range(int(input())):
	input()
	test = list(map(int, input().split()))
	print(f'{A(test)}')


t = int(input())
for i in range(t):
	n = int(input())
	X = list(map(int, input().split()))
	u = 1
	for z in X:
		u *= z
	ans = u + (n - 1)
	ans = ans * 2022
	print(ans)


import math
t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	ans = math.prod(a)
	ans += n - 1
	ans *= 2022
	print(ans)


k = int(input())
for n in range(k):
	z = int(input())
	a = list(map(int, input().rstrip().split()))
	p = 1
	for i in a:
		p *= i
	p += z - 1
	p *= 2022
	print(p)


def solve(lst):
	prod = 1
	for number in lst:
		prod *= number
	return (prod + len(lst) - 1) * 2022
t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	print(solve(lst))


t = int(input())
while t > 0:
	n = int(input())
	a = [int(i) for i in input().split()]
	p = 1
	for i in a:
		p *= i
	print((p + n - 1) * 2022)
	t -= 1


import math

class Solution:

	def __init__(self) -> None:
		pass

	def read(self):
		self.n = int(input())
		self.arr = list(map(int, input().split()))

	def solve(self):
		ans = 1
		for value in self.arr:
			ans *= value
		print((ans + self.n - 1) * 2022)
test = int(input())
for _ in range(test):
	testcase = Solution()
	testcase.read()
	testcase.solve()


for _ in range(int(input())):
	n = int(input())
	x = 1
	for i in map(int, input().split()):
		x *= i
	print((n + x - 1) * 2022)


import math
tests = int(input())
for t in range(tests):
	n = int(input())
	arr = input()
	arr = arr.split(' ')
	arr = [int(a) for a in arr]
	prod = math.prod(arr) + n - 1
	print(2022 * prod)


tk_Rf = int(input())
for _j in range(tk_Rf):
	c_Df = input()
	a_ra_Y = list(map(int, input().split()))
	f_Gjk = len(a_ra_Y) - 1
	P_kl_H = 1
	for j in a_ra_Y:
		P_kl_H *= j
	P_kl_H += f_Gjk
	print(P_kl_H * 2022)


from functools import reduce
from operator import mul
t = int(input())
for _ in range(t):
	(n, a) = (int(input()), (int(i) for i in input().split()))
	res = 2022 * (reduce(mul, a) + n - 1)
	print(res)


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(a, n):
	s = 1
	for x in a:
		s *= x
	s = s + n - 1
	return 2022 * s
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(a, n))


for q in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	cur = 1
	for item in arr:
		cur *= item
	print(2022 * (n - 1 + cur))


for i in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	result = 1
	for x in arr:
		result *= x
	result += n - 1
	print(result * 2022)


from functools import reduce
t = int(input())
for e in range(t):
	n = int(input())
	data = list(map(int, input().split()))
	print((reduce(lambda x, y: x * y, data) + n - 1) * 2022)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	res = 1
	for x in l:
		res *= x
	print((res + len(l) - 1) * 2022)


def solve(A, n):
	product = 1
	for a in A:
		product *= a
	return product + n - 1
t = int(input())
for i in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	result = solve(A, n)
	print(2022 * result)


t = int(input())
for _ in range(t):
	n = int(input())
	vals = list(map(int, input().split()))
	ans = 1
	for v in vals:
		ans *= v
	ans += len(vals) - 1
	print(ans * 2022)


try:
	for _ in range(int(input())):
		n = int(input())
		lst = list(map(int, input().split()))
		ans = 1
		for i in lst:
			ans *= i
		print((ans + n - 1) * 2022)
except Exception as e:
	print(e)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	a = 1
	x = arr.count(0)
	if x == n:
		print(0)
		continue
	for i in arr:
		if i != 0:
			a *= i
	a += len(arr) - 1 - x
	print(a * 2022)


t = int(input())
for j in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	pr = 1
	for i in a:
		pr *= i
	print((pr + n - 1) * 2022)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 1
	for ele in arr:
		ans *= ele
	ans += len(arr) - 1
	print(ans * 2022)


t = int(input())
while t > 0:
	n = int(input())
	a = input()
	arr = a.split()
	res = 1
	for i in arr:
		res = res * int(i)
	res += len(arr) - 1
	print(res * 2022)
	t -= 1


tst = int(input())
for i in range(tst):
	num = int(input())
	arr = list(map(int, input().split()))
	mul = 1
	for j in range(num):
		mul = mul * arr[j]
	ans = 2022 * (mul + num - 1)
	print(ans)


n = int(input())
for _ in range(n):
	t = int(input())
	m = list(map(int, input().split()))
	sm = 1
	for i in m:
		sm = sm * i
	sm += t - 1
	print(sm * 2022)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	p = 1
	s = 0
	for item in l:
		p = item * p
	s = p + (n - 1)
	print(2022 * s)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	p = 1
	for j in l:
		p *= j
	print(2022 * (p + (len(l) - 1)))


for _ in range(int(input())):
	__ = input()
	inp1 = [int(i) for i in input().split()]
	z = 1
	for i in inp1:
		z = z * i
	print(2022 * (z + (len(inp1) - 1)))