Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef is attending math classes. On each day, the teacher gives him homework. Yesterday, the teacher gave Chef a sequence of positive integers and asked him to find the maximum product of two different elements of this sequence. This homework was easy for Chef, since he knew that he should select the biggest two numbers.

However, today, the homework is a little bit different. Again, Chef has a sequence of positive integers $A_{1}, A_{2}, \ldots, A_{N}$, but he should find two different elements of this sequence such that the sum of digits (in base $10$) of their product is maximum possible.

Chef thought, mistakenly, that he can still select the two largest elements and compute the sum of digits of their product. Show him that he is wrong by finding the correct answer ― the maximum possible sum of digits of a product of two different elements of the sequence $A$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of the input contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------  Output ------
For each test case, print a single line containing one integer ― the maximum sum of digits.

------  Constraints ------
$1 ≤ T ≤ 100$
$2 ≤ N ≤ 100$
$1 ≤ A_{i} ≤ 10^{4}$ for each valid $i$

------  Subtasks ------
Subtask #1 (100 points): original constraints

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

2

2 8

3 

8 2 8

3

9 10 11
----- Sample Output 1 ------ 
7

10

18
----- explanation 1 ------ 
Example case 1: The only two numbers Chef can choose are $2$ and $8$. Their product is $16$ and the sum of digits of $16$ is $7$.

Example case 2: Chef can choose $8$ and $8$; their product is $64$. Note that it is allowed to choose two different elements with the same value.

Example case 3: Chef can choose $9$ and $11$. Their product is $99$ and the sum of its digits is $18$. Note that choosing $10$ and $11$ will result in a larger product ($110$), but the sum of its digits is just $2$.

Difficulty: EASY
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
def digsum(s):
	count = 0
	for d in s:
		count += int(d)
	return count
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	max = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			test = digsum(str(a[i] * a[j]))
			if max < test:
				max = test
	print(max)


def diginum(s):
	count = 0
	for i in s:
		count += int(i)
	return count
number_test = int(input())
for _ in range(number_test):
	num = int(input())
	list_digit = list(map(int, input().split()))
	max = 0
	for i in range(num - 1):
		for j in range(i + 1, num):
			product = diginum(str(list_digit[i] * list_digit[j]))
			if max < product:
				max = product
	print(max)


t = int(input())
for _ in range(t):
	n = int(input())
	line = input()
	words = line.split()
	nums = [int(w) for w in words]
	c = 0
	for i in range(n):
		for j in range(i + 1, n):
			num = nums[i] * nums[j]
			string = str(num)
			digit = [int(s) for s in string]
			d = sum(digit)
			if d > c:
				c = d
	print(c)


for _ in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	x = sorted(b)
	L = []
	for i in range(a):
		for j in range(i + 1, a):
			d = 0
			c = x[i] * x[j]
			c = str(c)
			for k in c:
				d = d + int(k)
				L.append(d)
	print(max(L))


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	h = []
	for i in range(n):
		for j in range(i + 1, n):
			r = 0
			b = a[i] * a[j]
			for k in str(b):
				r += int(k)
				h.append(r)
	print(max(h))


goals = int(input())
for distractions in range(goals):
	aim = int(input())
	life = list(map(int, input().split()))
	wife = []
	for stress in range(aim):
		for death in range(stress + 1, aim):
			angel = life[stress] * life[death]
			celestial_angel = 0
			for love in str(angel):
				celestial_angel += int(love)
			wife.append(celestial_angel)
	print(max(wife))


T = int(input())
for i in range(T):
	N = int(input())
	l = list(map(int, input().split()))
	L = []
	for i in range(N):
		for j in range(i + 1, N):
			a = l[i] * l[j]
			b = 0
			for k in str(a):
				b += int(k)
			L.append(b)
	print(max(L))


t = int(input())

def sum_digit(n):
	if n <= 9:
		return n
	else:
		return n % 10 + sum_digit(n // 10)
for _ in range(t):
	n = int(input())
	array = list(map(int, input().split()))
	prod = -1
	for i in range(n):
		for j in range(i + 1, n):
			temp = sum_digit(array[i] * array[j])
			if temp > prod:
				prod = temp
	print(prod)


t = int(input())
for x in range(t):
	n = int(input())
	list = []
	final = 0
	num = input()
	li = num.split(' ')
	list = [int(x) for x in li]
	for i in range(n):
		for j in range(i + 1, n):
			sum = 0
			pro = str(list[i] * list[j])
			for z in pro:
				sum = sum + int(z)
			if sum > final:
				final = sum
	print(final)


def sum(x):
	t = 0
	while x != 0:
		t = t + x % 10
		x = x // 10
	return t
for i in range(int(input())):
	n = int(input())
	l = []
	a = list(map(int, input().split()))
	for i in range(n - 1):
		for j in range(i + 1, n):
			l.append(a[i] * a[j])
	g = 0
	for i in l:
		if sum(i) > g:
			g = sum(i)
	print(g)


from itertools import combinations

def sumDigits(no):
	return 0 if no == 0 else int(no % 10) + sumDigits(int(no / 10))
t = int(input())
for i in range(t):
	n = int(input())
	l = map(int, input().split())
	comb = list(combinations(l, 2))
	product = []
	sumOfProduct = []
	for i in comb:
		product.append(i[0] * i[1])
	for i in product:
		sumOfProduct.append(sumDigits(i))
	print(max(sumOfProduct))


t = int(input(''))

def add_digits(a):
	summation = 0
	while a != 0:
		summation += a % 10
		a = a // 10
	return summation
for x in range(t):
	e = int(input(''))
	n = [int(y) for y in input('').split()]
	l = []
	final = []
	for y in range(len(n)):
		for u in range(y + 1, len(n)):
			l.append(n[y] * n[u])
	for y in l:
		result = add_digits(y)
		final.append(result)
	print(max(final))


def digit_sum(n):
	return sum((int(d) for d in str(n)))
tt = int(input())
for _ in range(tt):
	n = int(input())
	a = list(map(int, input().split()))
	max_digit_sum = -1
	for i in range(n):
		for j in range(i + 1, n):
			product = a[i] * a[j]
			digit_sum_product = digit_sum(product)
			if digit_sum_product > max_digit_sum:
				max_digit_sum = digit_sum_product
	print(max_digit_sum)


def tot(d):
	t = 0
	while d > 0:
		t += d % 10
		d = d // 10
	return t
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	l = []
	m = 0
	for i in range(n):
		for j in a[i + 1:]:
			p = a[i] * j
			if tot(p) > m:
				m = tot(p)
	print(m)


t = int(input())
for i in range(t):
	n = int(input())
	m = 0
	A = list(map(int, input().split()))
	for i in range(n):
		for j in range(i + 1, n):
			s = A[i] * A[j]
			a = 0
			while s != 0:
				a += s % 10
				s = s // 10
			if m < a:
				m = a
	print(m)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	l = []
	for j in range(len(a)):
		for k in range(j + 1, len(a)):
			z = a[j] * a[k]
			s = str(z)
			sum = 0
			for p in s:
				sum = sum + int(p)
			l.append(sum)
	print(max(l))


for j in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	l = []
	for j in range(N - 1):
		for k in range(j + 1, N):
			l.append(A[j] * A[k])
	l1 = []
	for j in l:
		c = str(j)
		s = 0
		for k in c:
			s = s + int(k)
		l1.append(s)
	print(max(l1))


def ds(s):
	count = 0
	d = 0
	v = int(s)
	while v > 0:
		d = v % 10
		count += d
		v //= 10
	return count
t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	max = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			c = ds(str(a[i] * a[j]))
			if max < c:
				max = c
	print(max)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	m = 0
	for i in range(n):
		for j in range(n):
			if i != j:
				mul = int(a[i] * a[j])
				k = str(mul)
				su = 0
				for l in k:
					su += int(l)
				m = max(m, su)
	print(m)
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	l = []
	s = input()
	l = s.split()
	for i in range(n):
		l[i] = int(l[i])
	max = 0
	for i in range(n):
		for j in range(n):
			if i != j:
				mul = l[i] * l[j]
				s = str(mul)
				sum = 0
				for d in s:
					sum += int(d)
				if sum > max:
					max = sum
	print(max)


n = int(input())
for i in range(n):
	r = int(input())
	t = []
	gr = 0
	t = [int(a) for a in input().split()]
	for l in range(len(t)):
		for m in range(l + 1, len(t)):
			s1 = 0
			r = t[l] * t[m]
			while r > 0:
				d = r % 10
				s1 += d
				r = r // 10
			if s1 >= gr:
				gr = s1
	print(gr)


t = int(input())
for i in range(t):
	n = int(input())
	m = 0
	a = list(map(int, input().split()))
	for i in range(len(a)):
		for j in range(i + 1, len(a)):
			s = 0
			for k in str(a[i] * a[j]):
				s += int(k)
			if m < s:
				m = s
	print(m)


def sdigit(h):
	s = 0
	while h > 0:
		rem = h % 10
		s += rem
		h = h // 10
	return s
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	k = []
	for i in range(n - 1):
		for j in range(i + 1, n):
			k.append(sdigit(l[i] * l[j]))
	print(max(k))


def sumdigits(num):
	n = num
	sumval = 0
	while n != 0:
		digit = n % 10
		sumval += digit
		n = n // 10
	return sumval
for _ in range(int(input())):
	N = int(input())
	nolist = list(map(int, input().split()))
	largest = 0
	for i in range(N - 1):
		for j in range(i + 1, N):
			num = nolist[i] * nolist[j]
			sumval = sumdigits(num)
			if largest < sumval:
				largest = sumval
	print(largest)


for _ in range(int(input())):
	n = int(input())
	m = [int(i) for i in input().split()]
	x = [sum([int(i) for i in str(m[i] * m[j]).strip()]) for i in range(n) for j in range(i + 1, n)]
	print(max(x))


def sumnum(strnumber):
	number = 0
	for digit in strnumber:
		number += int(digit)
	return number
for t in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split(' ')))
	s = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			num = nums[i] * nums[j]
			strnum = str(num)
			numb = sumnum(strnum)
			if numb > s:
				s = numb
	print(s)


t = int(input())

def sumdigits(x):
	sum = 0
	s = str(x)
	for i in s:
		sum += int(i)
	return sum
for i in range(t):
	n = int(input())
	L = list(map(int, input().split()))
	P = []
	S = []
	for j in range(len(L)):
		for k in range(j + 1, len(L)):
			P.append(L[j] * L[k])
	for item in P:
		S.append(sumdigits(item))
	print(max(S))


def sumDigits(number):
	num = 0
	for digit in number:
		num += int(digit)
	return num
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	s = 0
	sumdig = 0
	for i in range(n):
		for j in range(i + 1, n):
			prod = a[i] * a[j]
			prodstr = str(prod)
			product = sumDigits(prodstr)
			if product > s:
				s = product
				sumdig = product
				continue
	print(sumdig)


def getSum(n):
	sum = 0
	for digit in str(n):
		sum += int(digit)
	return sum
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = max(a)
	a.sort()
	c = 0
	s = 0
	s1 = 0
	for i in range(n):
		for j in range(i + 1, n):
			c = a[i] * a[j]
			s = getSum(c)
			if s > s1:
				s1 = s
			else:
				continue
	print(s1)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	l = []
	for i in range(0, n):
		for j in range(i + 1, n):
			pro = a[i] * a[j]
			maxsum = 0
			while pro != 0:
				maxsum = maxsum + pro % 10
				l.append(maxsum)
				pro = pro // 10
	print(max(l))


T = int(input())
for _ in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	d = []
	for i in range(n):
		for j in range(i + 1, n):
			p = A[i] * A[j]
			s = 0
			while p > 0:
				s += p % 10
				p //= 10
			d.append(s)
	print(max(d))


from itertools import combinations
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	comb = combinations(arr, 2)
	pqr = []
	for i in comb:
		abc = 1
		for j in i:
			abc *= j
		pqr.append(abc)
	s = []
	for i in set(pqr):
		x = list(str(i))
		ans = 0
		for j in x:
			ans += int(j)
		s.append(ans)
	print(max(s))


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	m = 0
	for j in range(len(a)):
		for k in range(len(a)):
			if j != k:
				d = a[j] * a[k]
				d = [int(x) for x in list(str(d))]
				d = sum(d)
				if d > m:
					m = d
	print(m)


t = int(input())
for it in range(t):
	n = int(input())
	a = list(map(int, input().split()))

	def digs(p):
		x = p
		sum = 0
		while x != 0:
			sum += x % 10
			x = x // 10
		return sum
	maxsum = 0
	for i in range(n):
		for j in range(i + 1, n):
			if digs(a[i] * a[j]) > maxsum:
				maxsum = digs(a[i] * a[j])
	print(maxsum)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	for i in range(n):
		for j in range(i + 1, n):
			c = a[i] * a[j]
			s = 0
			while c > 0:
				r = c % 10
				c = c // 10
				s = s + r
			b.append(s)
	print(max(b))


from itertools import combinations
t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	if len(s) == 2:
		p = 1
		sum = 0
		for k in s:
			p *= k
		p = str(p)
		for m in p:
			sum += int(m)
		print(sum)
	else:
		comb = list(set(tuple(sorted(combinations(s, 2)))))
		d = {}
		for i in comb:
			product = 1
			sum = 0
			for j in i:
				product *= j
			p = str(product)
			for k in p:
				sum += int(k)
			d[i] = sum
		print(max(list(d.values())))


n = int(input())
while n != 0:
	lst = []
	mul = []
	a = int(input())
	my_list = input().split()
	lst = [int(item) for item in my_list]
	for i in range(0, a):
		for j in range(i + 1, a):
			mul.append(lst[i] * lst[j])
	max = 0
	for i in mul:
		p = 0
		j = i
		while j != 0:
			p = p + j % 10
			j //= 10
		if p > max:
			max = p
	print(max)
	n -= 1


def sum_digit(n):
	return sum([int(x) for x in str(n)])
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = 0
	for i in range(n):
		for j in range(i + 1, n):
			ans = max([ans, sum_digit(a[i] * a[j])])
	print(ans)


T = int(input())
for i in range(T):
	N = int(input())
	d = []
	l = list(map(int, input().split()))
	for i in range(N):
		for j in range(i + 1, N):
			p = l[i] * l[j]
			s = 0
			while p > 0:
				s += p % 10
				p //= 10
			d.append(s)
	print(max(d))


def sum_digit(n):
	ds = 0
	for i in str(n):
		ds += int(i)
	return ds
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = 0
	for i in range(n):
		for j in range(n):
			if j != i:
				s = max(sum_digit(l[i] * l[j]), s)
	print(s)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	dig_root = 0
	for i in range(N):
		for j in range(i + 1, N):
			num = A[i] * A[j]
			root = 0
			while num > 0:
				root += num % 10
				num //= 10
			dig_root = max(root, dig_root)
	print(dig_root)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	dig_root = 0
	for i in range(N):
		for j in range(i + 1, N):
			num = A[i] * A[j]
			root = 0
			for k in str(num):
				root += int(k)
			dig_root = max(root, dig_root)
	print(dig_root)


def sums(n):
	r = 0
	while n > 0:
		r += n % 10
		n = n // 10
	return r
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = 0
	for i in range(n):
		for j in range(i + 1, n):
			c = max(c, sums(a[i] * a[j]))
	print(c)


goals = int(input())
for distractions in range(goals):
	wife = int(input())
	List = list(map(int, input().split()))
	c = 0
	for final in range(len(List)):
		for f in range(final + 1, len(List)):
			d = 0
			if d < List[final] * List[f]:
				d = List[final] * List[f]
			count = 0
			for i in str(d):
				count += int(i)
			if c < count:
				c = count
	print(c)


a = int(input())
while a > 0:
	a = a - 1
	size = int(input())
	lst = list(map(int, input().split(' ')))
	outlst = []
	for i in range(size):
		for j in range(i + 1, size):
			mul = lst[i] * lst[j]
			sum_b = 0
			while mul > 0:
				sum_b = sum_b + mul % 10
				mul = mul // 10
			outlst.append(sum_b)
	outlst.sort()
	indx = len(outlst)
	out_val = outlst[indx - 1]
	print(out_val)


def sum(x):
	d = 0
	for i in str(x):
		d += int(i)
	return d
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	maxi = 0
	for i in range(n):
		for j in range(i + 1, n):
			c = a[i] * a[j]
			e = sum(str(c))
			if e > maxi:
				maxi = e
	print(maxi)


from itertools import combinations
try:
	for _ in range(int(input())):
		N = int(input())
		L = list(map(int, input().split()))
		max_sum = 0
		for i in combinations(L, 2):
			p = i[0] * i[1]
			s = 0
			for d in list(str(p)):
				s += int(d)
			if s > max_sum:
				max_sum = s
		print(max_sum)
except:
	pass


def digit_sum(n):
	res = 0
	while n > 0:
		res += n % 10
		n = n // 10
	return res
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	max_digit_sum_product = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			temp_sum = digit_sum(l[i] * l[j])
			if temp_sum > max_digit_sum_product:
				max_digit_sum_product = temp_sum
	print(max_digit_sum_product)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split(' ')))
	p = []
	for i in range(0, n):
		for j in range(i + 1, n):
			x = a[i] * a[j]
			p.append(x)
		for j in range(0, i):
			x = a[i] * a[j]
			p.append(x)
	g = []
	for i in p:
		sum = 0
		while i != 0:
			r = i % 10
			i = i // 10
			sum = sum + r
			g.append(sum)
	x = max(g)
	print(x)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = 0
	for i in range(n):
		for j in range(n):
			if i == j:
				continue
			p = a[i] * a[j]
			s = 0
			while p > 0:
				s = s + p % 10
				p = p // 10
			if s > m:
				m = s
	print(m)


t = int(input())
for i in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	product = []
	for i in range(0, n):
		for j in range(i + 1, n):
			p = x[i] * x[j]
			product.append(p)
		for j in range(0, i):
			p = x[i] * x[j]
			product.append(p)
	great = []
	for i in product:
		sum = 0
		while i != 0:
			rem = i % 10
			i = i // 10
			sum = sum + rem
			great.append(sum)
	ans = max(great)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))[:n]
	max = 0
	for i in range(len(l)):
		for j in range(len(l)):
			if i != j:
				pro = l[i] * l[j]
				sum = 0
				while pro != 0:
					sum = sum + pro % 10
					pro = pro // 10
					if sum > max:
						max = sum
	print(max)


def sum(n):
	s = str(n)
	x = 0
	for i in s:
		x += int(i)
	return x
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = []
	x = 1
	for i in a:
		for j in range(x, n):
			l.append(sum(i * a[j]))
		x = x + 1
	print(max(l))


for t in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))
	max = 0
	for i in range(n):
		for j in range(n):
			if i != j:
				temp = m[i] * m[j]
				sum = 0
				while temp != 0:
					rem = temp % 10
					sum = sum + rem
					temp = temp // 10
				if sum > max:
					max = sum
	print(max)


test = int(input())
for i in range(test):
	n = int(input())
	num = list(map(int, input().split(' ')))
	maxx = 0
	for j in range(len(num)):
		for k in range(j + 1, len(num)):
			product = num[j] * num[k]
			s = str(product)
			summ = 0
			for i in s:
				summ = summ + int(i)
			if summ >= maxx:
				maxx = summ
	print(maxx)


def digsum(x):
	dsum = 0
	for j in str(x):
		dsum += int(j)
	return dsum
from itertools import combinations
for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	dsum = 0
	dsummax = 0
	for i in combinations(a, 2):
		dsum = digsum(i[0] * i[1])
		if dsum > dsummax:
			dsummax = dsum
	print(dsummax)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	l = []
	k = []
	v = []
	for i in range(n):
		for j in range(i + 1, n):
			k.append(a[i] * a[j])
	for pav in k:
		d = 0
		for o in str(pav):
			d = d + int(o)
		v.append(d)
	print(max(v))


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	c = []
	d = []
	for i in range(len(a)):
		for j in range(i + 1, len(a)):
			k = a[i] * a[j]
			c.append(k)
	for i in c:
		sum = 0
		while i > 0:
			res = i % 10
			sum = sum + res
			i = i // 10
		d.append(sum)
	print(max(d))


t = int(input())
for ni in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = list()
	for i in range(n):
		for j in range(n):
			if i == j:
				continue
			else:
				l1.append(str(l[i] * l[j]))
	l2 = [0] * len(l1)
	k = 0
	for i in l1:
		for j in range(len(i)):
			l2[k] = l2[k] + int(i[j])
		k = k + 1
	print(max(l2))


for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	s = 0
	a = []
	for i in range(N - 1):
		for j in range(i + 1, N):
			a.append(A[i] * A[j])
	b = []
	for x in a:
		for digit in str(x):
			s += int(digit)
		b.append(s)
		s = 0
	print(max(b))