You are given an array of integers a_1,a_2,…,a_n. Find the maximum possible value of a_ia_ja_ka_la_t among all five indices (i, j, k, l, t) (i<j<k<l<t).

Input

The input consists of multiple test cases. The first line contains an integer t (1≤ t≤ 2 ⋅ 10^4) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n (5≤ n≤ 10^5) — the size of the array.

The second line of each test case contains n integers a_1,a_2,…,a_n (-3× 10^3≤ a_i≤ 3× 10^3) — given array.

It's guaranteed that the sum of n over all test cases does not exceed 2⋅ 10^5.

Output

For each test case, print one integer — the answer to the problem.

Example

Input


4
5
-1 -2 -3 -4 -5
6
-1 -2 -3 1 2 -1
6
-1 0 0 0 -1 -1
6
-9 -7 -5 -3 -2 1


Output


-120
12
0
945

Note

In the first test case, choosing a_1,a_2,a_3,a_4,a_5 is a best choice: (-1)⋅ (-2) ⋅ (-3)⋅ (-4)⋅ (-5)=-120.

In the second test case, choosing a_1,a_2,a_3,a_5,a_6 is a best choice: (-1)⋅ (-2) ⋅ (-3)⋅ 2⋅ (-1)=12.

In the third test case, choosing a_1,a_2,a_3,a_4,a_5 is a best choice: (-1)⋅ 0⋅ 0⋅ 0⋅ (-1)=0.

In the fourth test case, choosing a_1,a_2,a_3,a_4,a_6 is a best choice: (-9)⋅ (-7) ⋅ (-5)⋅ (-3)⋅ 1=945.
import sys
sys.setrecursionlimit(10000)
# default is 1000 in python

# increase stack size as well (for hackerrank)
# import resource
# resource.setrlimit(resource.RLIMIT_STACK, (resource.RLIM_INFINITY, resource.RLIM_INFINITY))


t = int(input())
# t = 1

for _ in range(t):
	n = int(input())

	# u, v = list(map(int, input().split()))

	a = list(map(int, input().split()))

	b = []
	for i in a:
		if i < 0:
			b.append([-i, -1])
		else:
			b.append([i, 1])
	b.sort(key=lambda x: x[0], reverse=True)

	sign_prod = b[0][1] * b[1][1] * b[2][1] * b[3][1] * b[4][1]

	if sign_prod > 0:
		prod = b[0][0] * b[1][0] * b[2][0] * b[3][0] * b[4][0]
	else:
		smallest_neg = None
		smallest_pos = None
		for i in range(4,-1,-1):
			if smallest_neg is None and b[i][1] < 0:
				smallest_neg = i
			if smallest_pos is None and b[i][1] > 0:
				smallest_pos = i

		if len(b) == 5:
				prod = -1 * b[0][0] * b[1][0] * b[2][0] * b[3][0] * b[4][0]			
		else:
			if b[4][1] < 0 and b[5][1] > 0:
				prod = b[0][0] * b[1][0] * b[2][0] * b[3][0] * b[5][0]
			elif b[4][1] > 0 and b[5][1] < 0:
				prod = b[0][0] * b[1][0] * b[2][0] * b[3][0] * b[5][0]
			elif b[4][1] > 0 and b[5][1] > 0:
				prod1 = (b[0][0] * b[1][0] * b[2][0] * b[3][0] * b[4][0] * b[5][0]) // b[smallest_neg][0]
				prod2 = prod1
				for i in range(6, len(b)):
					if b[i][1] < 0:
						prod2 = b[0][0] * b[1][0] * b[2][0] * b[3][0] * b[i][0]
						break
				prod = max(prod1, prod2)
			elif b[4][1] < 0 and b[5][1] < 0:
				if smallest_pos is not None:
					prod1 = (b[0][0] * b[1][0] * b[2][0] * b[3][0] * b[4][0] * b[5][0]) // b[smallest_pos][0]
				else:
					prod1 = -1*(b[n-1][0] * b[n-2][0] * b[n-3][0] * b[n-4][0] * b[n-5][0])
				prod2 = prod1
				for i in range(6, len(b)):
					if b[i][1] > 0:
						prod2 = b[0][0] * b[1][0] * b[2][0] * b[3][0] * b[i][0]
						break
				prod = max(prod1, prod2)
	print(prod)

# try:
	# raise Exception
# except:
	# print("-1")


# from itertools import combinations 
# all_combs = list(combinations(range(N), r))



# from collections import OrderedDict 
# mydict = OrderedDict() 


# thenos.sort(key=lambda x: x[2], reverse=True)


# int(math.log(max(numbers)+1,2))


# 2**3 (power)


# a,t = (list(x) for x in zip(*sorted(zip(a, t))))


# to copy lists use:
# import copy
# copy.deepcopy(listname)

# pow(p, si, 1000000007) for modular exponentiation


# my_dict.pop('key', None)
# This will return my_dict[key] if key exists in the dictionary, and None otherwise.


# bin(int('010101', 2))

# Binary Search
# from bisect import bisect_right
# i = bisect_right(a, ins)
