Chef likes cooking. But more than that, he likes to give gifts. And now he wants to give his girlfriend an unforgettable gift. But unfortunately he forgot the password to the safe where the money he saved for the gift is kept.

But he knows how to hack the safe. To do this, you need to correctly answer questions asked by the embedded computer. The computer is very strange, and asks special questions, sometimes it can ask about 10000 question (really weird). Because of this, Chef wants you to write a program that will help him to crack the safe.

The questions are different, but there is only one type of question. Several numbers are given and between them one of three characters: *, +, - can be inserted. Note that in this case there is no priority for the operators, that is, if + is the before multiplication, you must first execute the operation of addition, and then multiplication (1 - 2 * 3 must be interpreted as (1 - 2) * 3 = -3 and not -5). The computer asks the minimum possible value of any valid expression.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The first line of each test case contains a positive integer N. The second line contains N space separated integers A_{1}, A_{2}, ..., A_{N} denoting the expression without the operators.
 
------ Output ------ 

For each test case, output a single line containing the minimal value of given expression. 

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10$
$-9 ≤ A_{i} ≤ 9 .
$ 

------  Scoring  ------ 

Subtask 1 (15 points):  1 ≤ T ≤ 10  

Subtask 2 (10 points):  1 ≤ N ≤ 3    

Subtask 3 (20 points):  1 ≤ A_{i} ≤ 5. 

Subtask 4 (35 points): 1 ≤ T  ≤ 10^{4} 
 
Subtask 5 (20 points):  Look at constraints.         

----- Sample Input 1 ------ 
2
3
1 2 3
1
9
----- Sample Output 1 ------ 
-4
9
----- explanation 1 ------ 
Example case 1:  1-2-3 = -4

Difficulty: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	best = a[0]
	worst = a[0]
	for i in range(1, n):
		newbest = best
		newworst = worst
		newbest = max(newbest, best + a[i])
		newbest = max(newbest, worst + a[i])
		newbest = max(newbest, best - a[i])
		newbest = max(newbest, worst - a[i])
		newbest = max(newbest, best * a[i])
		newbest = max(newbest, worst * a[i])
		newworst = min(newworst, worst + a[i])
		newworst = min(newworst, best + a[i])
		newworst = min(newworst, worst - a[i])
		newworst = min(newworst, best - a[i])
		newworst = min(newworst, worst * a[i])
		newworst = min(newworst, best * a[i])
		best = newbest
		worst = newworst
	print(worst)


import re
from functools import reduce
INPUT_PAT = re.compile('(-?\\d+)\\s*')

def smallest_expression(a, b):
	return (min(a[0] - b, a[0] + b, a[0] * b, a[1] * b), max(a[1] - b, a[1] + b, a[0] * b, a[1] * b))
num_examples = int(input())
for _ in range(num_examples):
	n = int(input())
	(a0, *a) = (int(i) for i in INPUT_PAT.findall(input()))
	print(reduce(smallest_expression, a, (a0, a0))[0])


def eval(A):
	best_eval = [0] * (len(A) + 1)
	worst_eval = [0] * (len(A) + 1)
	best_eval[0] = A[0]
	worst_eval[0] = A[0]
	for i in range(1, len(A)):
		if A[i] > 0:
			best_eval[i] = max(best_eval[i - 1] + A[i], best_eval[i - 1] - A[i], best_eval[i - 1] * A[i])
			worst_eval[i] = min(worst_eval[i - 1] + A[i], worst_eval[i - 1] - A[i], worst_eval[i - 1] * A[i])
		else:
			best_eval[i] = max(best_eval[i - 1] + A[i], best_eval[i - 1] - A[i], worst_eval[i - 1] * A[i])
			worst_eval[i] = min(worst_eval[i - 1] + A[i], worst_eval[i - 1] - A[i], best_eval[i - 1] * A[i])
	return worst_eval[len(A) - 1]
ot = []
test = int(input())
for i in range(test):
	l = []
	e = int(input())
	l = list(map(int, input().split()))
	ot.append(l)
for i in ot:
	print(eval(i))


N = int(input())
for i in range(N):
	M = int(input())
	arr = list(map(int, input().split()))
	dp = [[0, 0] for x in range(M)]
	dp[0][0] = dp[0][1] = arr[0]
	for j in range(1, M):
		ch = [0 for x in range(6)]
		for k in range(2):
			ch[k * 3] = dp[j - 1][k] + arr[j]
			ch[k * 3 + 1] = dp[j - 1][k] - arr[j]
			ch[k * 3 + 2] = dp[j - 1][k] * arr[j]
		ch.sort()
		dp[j][0] = ch[0]
		dp[j][1] = ch[5]
	print(dp[M - 1][0])


test = int(input())
for why in range(test):
	n = int(input())
	arr = [int(k) for k in input().split()]
	mini_arr = [0 for i in range(n)]
	max_arr = [0 for i in range(n)]
	mini_arr[0] = arr[0]
	max_arr[0] = arr[0]
	for i in range(1, len(arr)):
		if arr[i] > 0:
			mini_arr[i] = min(mini_arr[i - 1] + arr[i], mini_arr[i - 1] - arr[i], mini_arr[i - 1] * arr[i])
			max_arr[i] = max(max_arr[i - 1] + arr[i], max_arr[i - 1] - arr[i], max_arr[i - 1] * arr[i])
		else:
			mini_arr[i] = min(mini_arr[i - 1] + arr[i], mini_arr[i - 1] - arr[i], max_arr[i - 1] * arr[i])
			max_arr[i] = max(max_arr[i - 1] + arr[i], max_arr[i - 1] - arr[i], mini_arr[i - 1] * arr[i])
	print(mini_arr[n - 1])


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	arr = list(map(int, input().strip().split()))[:n]
	mini = [0 for i in range(n)]
	maxi = [0 for i in range(n)]
	mini[0] = arr[0]
	maxi[0] = arr[0]
	for i in range(1, len(arr)):
		if arr[i] > 0:
			mini[i] = min(mini[i - 1] + arr[i], mini[i - 1] - arr[i], mini[i - 1] * arr[i])
			maxi[i] = max(maxi[i - 1] + arr[i], maxi[i - 1] - arr[i], maxi[i - 1] * arr[i])
		else:
			mini[i] = min(mini[i - 1] + arr[i], mini[i - 1] - arr[i], maxi[i - 1] * arr[i])
			maxi[i] = max(maxi[i - 1] + arr[i], maxi[i - 1] - arr[i], mini[i - 1] * arr[i])
	print(mini[n - 1])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	best = []
	worst = []
	best.append(a[0])
	worst.append(a[0])
	for i in range(1, n):
		if a[i] > 0:
			best.append(max([best[i - 1] + a[i], best[i - 1] - a[i], best[i - 1] * a[i]]))
			worst.append(min([worst[i - 1] + a[i], worst[i - 1] - a[i], worst[i - 1] * a[i]]))
		else:
			best.append(max([best[i - 1] + a[i], best[i - 1] - a[i], worst[i - 1] * a[i]]))
			worst.append(min([worst[i - 1] + a[i], worst[i - 1] - a[i], best[i - 1] * a[i]]))
	print(worst[n - 1])


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	maxval = [0] * n
	maxval[0] = arr[0]
	minval = [0] * n
	minval[0] = arr[0]
	for i in range(1, n):
		if arr[i] > 0:
			maxval[i] = max(maxval[i - 1] + arr[i], maxval[i - 1] - arr[i], maxval[i - 1] * arr[i])
			minval[i] = min(minval[i - 1] + arr[i], minval[i - 1] - arr[i], minval[i - 1] * arr[i])
		else:
			maxval[i] = max(maxval[i - 1] + arr[i], maxval[i - 1] - arr[i], minval[i - 1] * arr[i])
			minval[i] = min(minval[i - 1] + arr[i], minval[i - 1] - arr[i], maxval[i - 1] * arr[i])
	print(minval[-1])


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	arr = list(map(int, input().strip().split()))[:n]
	minsofar = [0 for i in range(n)]
	maxsofar = [0 for i in range(n)]
	minsofar[0] = arr[0]
	maxsofar[0] = arr[0]
	for i in range(1, n):
		if arr[i] > 0:
			minsofar[i] = min(minsofar[i - 1] + arr[i], minsofar[i - 1] - arr[i], minsofar[i - 1] * arr[i])
			maxsofar[i] = max(maxsofar[i - 1] + arr[i], maxsofar[i - 1] - arr[i], maxsofar[i - 1] * arr[i])
		else:
			minsofar[i] = min(minsofar[i - 1] + arr[i], minsofar[i - 1] - arr[i], maxsofar[i - 1] * arr[i])
			maxsofar[i] = max(maxsofar[i - 1] + arr[i], maxsofar[i - 1] - arr[i], minsofar[i - 1] * arr[i])
	print(minsofar[n - 1])


for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = []
	b.append(a[0])
	w = []
	w.append(a[0])
	for i in range(1, n):
		if a[i] > 0:
			b.append(max(b[i - 1] + a[i], max(b[i - 1] - a[i], b[i - 1] * a[i])))
			w.append(min(w[i - 1] + a[i], min(w[i - 1] - a[i], w[i - 1] * a[i])))
		else:
			b.append(max(b[i - 1] + a[i], max(b[i - 1] - a[i], w[i - 1] * a[i])))
			w.append(min(w[i - 1] + a[i], min(w[i - 1] - a[i], b[i - 1] * a[i])))
	print(w[n - 1])


def doshit(arr, val):
	if len(arr) == 1:
		v = arr[0]
		l = [v + val, v - val, v * val]
		return (max(l), min(l))
	else:
		(ma, mi) = doshit(arr[:-1], arr[-1])
		l = [ma + val, ma - val, ma * val, mi + val, mi - val, mi * val]
		return (max(l), min(l))
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().strip().split(' ')))
	if len(arr) == 1:
		print(arr[0])
	else:
		(ma, mi) = doshit(arr[:-1], arr[-1])
		print(mi)