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.
"""
- math -
from math import factorial
from math import gcd
from math import pi
large_p = 10**9 + 7
from itertools import accumulate # 累積和
from operator import mul
- other -
from collections import Counter
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
from operator import itemgetter
from functools import reduce
- list -
from copy import deepcopy
from collections import deque
from heapq import heapify, heappop, heappush
- output -
p2d = lambda x: print(*x, sep="\n")
p2line = lambda x: print(*x, sep=" ")
print(*list1, sep="\n")
- input -
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
= map(int, input().split())
= [tuple(map(int, input().split())) for _ in range(n)]
m = map(int, read().split()) /ab = zip(m, m) /for a, b in ab:
- run -
sys.setrecursionlimit(10**6)
from time import sleep
"""
# ATC7


import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import combinations
def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = tuple(map(int, input().split()))
        if n == 5:
            print(a[0] * a[1] * a[2] * a[3] * a[4])
        elif n - a.count(0) < 5:
            print(0)
        else:
            numm = len([ea for ea in a if ea < 0])
            ap = [ea for ea in a if ea > 0]
            am = [ea for ea in a if ea < 0]
            ap.sort()
            am.sort()
            ap = ap[-5:]
            am1n = min(4, numm)
            am1 = am[:am1n]
            am = am[am1n:]
            aa = ap + am1 + am[-5:]
            com = tuple(combinations(aa, 5))
            com0 = com[0]
            r = com0[0] * com0[1] * com0[2] * com0[3] * com0[4]
            for come in com:
                r = max(r, come[0] * come[1] * come[2] * come[3] * come[4])
            if r < 0:
                if 0 in a:
                    print(0)
                else:
                    print(r)
            else:
                print(r)

if __name__ == '__main__':
    main()
