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.
def getMagnitude(pair):
    return pair[0]

def getProductOfElems(elems):
    numElems = len(elems)
    product = 1
    for index in range(numElems):
        elem = elems[index]
        product *= (elem[0] * elem[1])
    return product

def getNegativeNonNegativeElements(elems):
    nonNegativeElems = []
    negativeElems = []
    for index in range(N):
        elem = elems[index]
        if elem[1] == -1:
            negativeElems.append(elem)
        else:
            nonNegativeElems.append(elem)
    return negativeElems, nonNegativeElems


def findMaximumProductOf5(arrayWithMagnitudeAndSign):
    N = len(arrayWithMagnitudeAndSign)

    # base cases
    if N < 5:
        return 0
    elif N == 5:
        return getProductOfElems(arrayWithMagnitudeAndSign)

    # note that only lists with at least 6 elements get till here

    # sort elements by magnitude
    arrayWithMagnitudeAndSign.sort(key=getMagnitude, reverse=True)

    # separate out negative and non-negative
    negativeElems, nonNegativeElems = getNegativeNonNegativeElements(arrayWithMagnitudeAndSign)
    numNonNeg = len(nonNegativeElems)
    numNeg = len(negativeElems)

    # no non-negative element: find the product of negative elements with smallest magnitude
    if (numNonNeg == 0):
        return getProductOfElems(negativeElems[numNeg-5:numNeg])

    # product of 4 largest negative elements and largest non-negative element
    elif (numNonNeg == 1 or numNonNeg == 2):
        return nonNegativeElems[0][0] * getProductOfElems(negativeElems[0:4])

    # product of 5 largest non-negative elements
    elif (numNeg == 0 or numNeg == 1):
        return getProductOfElems(nonNegativeElems[0:5])


    # here, we have at least 2 negative, 3 non-negative elements
    # mixed product: product of 2 largest (by magnitude) negative
    # and three largest non-negative elements
    mixedProduct = getProductOfElems(negativeElems[0:2]) * getProductOfElems(nonNegativeElems[0:3])

    # mixed product
    if (numNeg < 4 and numNonNeg <= 4):
        return mixedProduct

    # max. out of mixed product, and product of 5 largest non-negative elements
    elif (numNeg < 4 and numNonNeg > 4):
        allNonNegProduct = getProductOfElems(nonNegativeElems[0:5])
        return max(allNonNegProduct, mixedProduct)


    # here, we have at least 4 negative, 3 non-negative elements
    # four negative product: product of largest non-negative and
    # four largest negative (by magnitude) elements
    fourNegProduct = nonNegativeElems[0][0] * getProductOfElems(negativeElems[0:4])

    # max. out of mixed product, four negative product
    if (numNonNeg <= 4):
        return max(fourNegProduct, mixedProduct)

    # max. out of mixed, four negative, all non-negative products
    allNonNegProduct = getProductOfElems(nonNegativeElems[0:5])
    return max(allNonNegProduct, fourNegProduct, mixedProduct)


# helper function to get (magnitude, sign) tuple for a number
def getMagnitudeAndSign(number):
    if number < 0:
        return (-number, -1)
    return (number, 1)

# main code: user input
T = int(input())
for t in range(T):
    N = int(input())
    arrayOfNumbers = list(map(int, input().split()))
    arrayWithMagnitudeAndSign = list(map(getMagnitudeAndSign, arrayOfNumbers))
    print(findMaximumProductOf5(arrayWithMagnitudeAndSign=arrayWithMagnitudeAndSign))