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 maxProductSubarrayOfSizeK(A , n , k):
    A.sort()
    product = 1

    # CASE I
    # If max element is 0 and
    # k is odd then max product will be 0
    if (A[n - 1] == 0 and (k & 1)):
        return 0

    # CASE II
    # If all elements are negative and
    # k is odd then max product will be
    # product of rightmost-subarray of size k
    if (A[n - 1] <= 0 and (k & 1)):
        for i in range(n - 1 , n - k - 1 , -1):
            product *= A[i]
        return product

    # else
    # i is current left pointer index
    i = 0

    # j is current right pointer index
    j = n - 1

    # CASE III
    # if k is odd and rightmost element in
    # sorted array is positive then it
    # must come in subsequence
    # Multiplying A[j] with product and
    # correspondingly changing j
    if (k & 1):
        product *= A[j]
        j -= 1
        k -= 1

    # CASE IV
    # Now k is even. So, Now we deal with pairs
    # Each time a pair is multiplied to product
    # ie.. two elements are added to subsequence
    # each time. Effectively k becomes half
    # Hence, k >>= 1 means k /= 2
    k >>= 1

    # Now finding k corresponding pairs to get
    # maximum possible value of product
    for itr in range(k):

        # product from left pointers
        left_product = A[i] * A[i + 1]

        # product from right pointers
        right_product = A[j] * A[j - 1]

        # Taking the max product from two
        # choices. Correspondingly changing
        # the pointer's position
        if (left_product > right_product):
            product *= left_product
            i += 2

        else:
            product *= right_product
            j -= 2

    # Finally return product
    return product


for _ in range(int(input())):
    n=int(input())
    A = list(map(int , input().split()))
    k=5
    print(maxProductSubarrayOfSizeK(A , n , k))

