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):
    if pair[1] == 1:
        return pair[0] + 0.5
    return pair[0]

def findMaximumProductOf5(arrayWithMagnitudeAndSignInfo):
    l = len(arrayWithMagnitudeAndSignInfo)
    arrayWithMagnitudeAndSignInfo.sort(key = getMagnitude, reverse=True)
    #print(arrayWithMagnitudeAndSignInfo)

    maxProduct = 1

    listOfBiggestTermIndices = [-1, -1, -1, -1, -1]
    for i in range(len(arrayWithMagnitudeAndSignInfo)):
        if arrayWithMagnitudeAndSignInfo[i][1] == 1:
            listOfBiggestTermIndices[0] = i
            break

    if listOfBiggestTermIndices[0] == -1:
        listOfBiggestTermIndices = [l-1, l-2, l-3, l-4, l-5]
        for termIndex in range(5):
            maxProduct *= (arrayWithMagnitudeAndSignInfo[listOfBiggestTermIndices[termIndex]][0] *
                           arrayWithMagnitudeAndSignInfo[listOfBiggestTermIndices[termIndex]][1])


    else:
        #print(listOfBiggestTermIndices[0])
        largest4Negative  = [-1, -1, -1, -1]
        largest4Positive = [-1, -1, -1, -1]

        neg4 = 0
        pos4 = 0

        i = 0
        while (neg4 < 4 and i < len(arrayWithMagnitudeAndSignInfo)):
            if i != listOfBiggestTermIndices[0] and arrayWithMagnitudeAndSignInfo[i][1] == -1:
                largest4Negative[neg4] = i
                neg4 += 1
            i += 1

        i = 0
        while (pos4 < 4 and i < len(arrayWithMagnitudeAndSignInfo)):
            if i != listOfBiggestTermIndices[0] and arrayWithMagnitudeAndSignInfo[i][1] == 1:
                largest4Positive[pos4] = i
                pos4 += 1
            i += 1

        largest2Negative = [largest4Negative[0], largest4Negative[1], largest4Positive[0], largest4Positive[1]]

        '''print(largest4Negative)
        print(largest4Positive)
        print(largest2Negative)'''

        product1 = 1
        for termIndex1 in range(4):
            product1 *= arrayWithMagnitudeAndSignInfo[largest4Negative[termIndex1]][0]

        product2 = 1
        for termIndex1 in range(4):
            product2 *= arrayWithMagnitudeAndSignInfo[largest4Positive[termIndex1]][0]

        product3 = 1
        for termIndex1 in range(4):
            product3 *= arrayWithMagnitudeAndSignInfo[largest2Negative[termIndex1]][0]

        if neg4 == 4 and pos4 == 4:
            maxProduct = arrayWithMagnitudeAndSignInfo[listOfBiggestTermIndices[0]][0] * max(product1, product2, product3)

        elif neg4 == 4 and pos4 >= 2:
            maxProduct = arrayWithMagnitudeAndSignInfo[listOfBiggestTermIndices[0]][0] * max(product1, product3)

        elif pos4 == 4 and neg4 >= 2:
            maxProduct = arrayWithMagnitudeAndSignInfo[listOfBiggestTermIndices[0]][0] * max(product2, product3)

        elif neg4 == 4:
            maxProduct = arrayWithMagnitudeAndSignInfo[listOfBiggestTermIndices[0]][0] * product1

        elif pos4 == 4:
            maxProduct = arrayWithMagnitudeAndSignInfo[listOfBiggestTermIndices[0]][0] * product2

        elif neg4 >= 2 and pos4 >= 2:
            maxProduct = arrayWithMagnitudeAndSignInfo[listOfBiggestTermIndices[0]][0] * product3

        else:
            listOfBiggestTermIndices = [l - 1, l - 2, l - 3, l - 4, l - 5]
            for termIndex in range(5):
                maxProduct *= (arrayWithMagnitudeAndSignInfo[listOfBiggestTermIndices[termIndex]][0] *
                               arrayWithMagnitudeAndSignInfo[listOfBiggestTermIndices[termIndex]][1])

    return maxProduct

def getMagnitudeAndSign(number):
    if number < 0:
        return (-number, -1)
    return (number, 1)


T = int(input())
for t in range(T):
    N = int(input())
    arrayOfNumbers = list(map(int, input().split()))
    arrayWithMagnitudeAndSignInfo = list(map(getMagnitudeAndSign, arrayOfNumbers))
    print(findMaximumProductOf5(arrayWithMagnitudeAndSignInfo=arrayWithMagnitudeAndSignInfo))