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.
# Answer Printing Module
def ans_if_list(ans):

    if isinstance(ans, str):
        return ans

    elif isinstance(ans, int):
        return ans

    else:
        return ' '.join(str(ans[i]) for i in range(len(ans)))

# For various input
def input_list(typ='int'):
    if typ == 'int':
        return list(map(int, input().split()))
    elif typ == 'str':
        return list(input())

# Question 2
def multiplyList(ls):
    # Multiply elements one by one
    res = 1
    for x in ls:
        res = res * x
    return res



t = int(input())

for q in range(t):
    l = int(input())
    ls = input_list()

    if l == 5:
        ans = multiplyList(ls)

    else:
        neg = list()
        z = list()
        pos = list()
        # O(n) - list
        for i in ls:
            if i > 0:
                pos.append(i)
            elif i == 0:
                z.append(i)
            else:
                neg.append(i)


        if len(pos) + len(neg) < 5 and len(z) >= 1:
            ans = 0

        elif len(pos) + len(neg) == 5:
            if len(neg) == 1 or len(neg) == 3 or len(neg) == 5:
                ans = 0
            else:
                # negative list lenght 2 or 4
                ans = multiplyList(pos+neg)

        else:
            neg = sorted(neg)
            pos = sorted(pos, reverse=True)

            if len(pos) >= 5:
                candidate = [
                    multiplyList(neg[0:4]) * pos[0],
                    multiplyList(neg[0:2]) * multiplyList(pos[0:3]),
                    multiplyList(pos[0:5])
                ]
                ans = max(candidate)

            elif len(pos) >= 3 and len(pos) < 5:
                candidate = [
                    multiplyList(neg[0:4]) * pos[0],
                    multiplyList(neg[0:2]) * multiplyList(pos[0:3])
                ]
                ans = max(candidate)

            elif len(pos) >= 1 and len(pos) < 3:
                candidate = [
                    multiplyList(neg[0:4]) * pos[0],
                ]
                ans = max(candidate)

            else:
                if len(z) >= 1:
                    ans = 0
                else:
                    ans = neg[-1] * neg[-2] * neg[-3] * neg[-4] * neg[-5]


    print(ans)
