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;input=sys.stdin.readline

def ff(l,N):
    if N == 5:
        r = 1
        for i in range(N):
            r *= l[i]
        return r
    c = 0
    m = 0
    ll = []
    for x in l:
        if x == 0:
            c += 1
        else:
            if x < 0:
                m += 1
            ll.append(x)
    N-=c
    if N < 5:
        return 0
    if m == N:
        if c == 0:
            ll.sort()
            R =1
            for i in range(5):
                R *= ll.pop()
#            print(R)
            return R
        return 0
    if N == 5:
        r = 1
        for i in range(N):
            r *= ll[i]
        return max(r, 0)
    l1, l2 = [], []
    for x in ll:
        if x > 0:
            l1.append(x)
        else:
            l2.append(x)
    l1.sort()
    l2.sort()
    l2 = l2[::-1]
#    print(l1, l2)
    R = l1.pop()
    y = []
    while len(l1)>=2:
        x = l1.pop()
        x *= l1.pop()
        y.append(x)
#    print(y)
    while len(l2)>=2:
        x = l2.pop()
        x *= l2.pop()
        y.append(x)
#    print(y)
    y.sort()
    R = R*y[-1]*y[-2]
    return R



T, = map(int, input().split())
for _ in range(T):
    N, = map(int, input().split())
    X = list(map(int, input().split()))
    print(ff(X, N))
