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
import math

# Constants
mod = 998244353

# Program Settings
cases = True


# Functions Settings
dynamic_factorial = False



# Pre-defined function
# Begin

# Testcase handler
def main(test_case = False):
    n = int(input()) if test_case else 1
    for _ in range(n):
        test()
        print()

# Binary method of power
def fast_pow(a:int, b:int):
    res = 1
    while b > 0:
        if b & 1:
            res *= a
        a *= a
        b >>= 1
    return res

# Combination of 2
def c2(n):
    return n * (n-1) // 2

# Get the list form of input
def get():
    return list(map(int, input().split()))

# Number of 1s in binary form
def bits(n: int):
    return list(bin(n)).count('1')

# For interactive problems
def flush():
    sys.stdout.flush()

# Print array and split it with space
def parr(arr):
    print(*arr, sep=' ')

# GCD (int a, int b)
# Return: value of GCD(a, b)
def gcd(a, b):
    while b:
        if b % a == 0:
            break
        tmp = a
        a = b % a
        b = tmp
    return a

# Extended GCD (int a, int b)
# Return: array of [GCD(a, b), [x0, y0]]
# Where a * x0 + b * y0 = 1
# If GCD(a, b) != 1 then return False
def ext_gcd(a: int, b: int):
    if (b == 0):
        return [a, [1, 0]]
 
    res = ext_gcd(b, a % b)
    g = res[0]
    if g != 1:
        return False
    x1 = res[1][0]
    y1 = res[1][1]
    x = y1
    y = x1 - y1 * (a // b)
 
    return [g, [x, y]]

# Get all different values of array a with their count
def get_set(a):
    res = {}
    for x in a:
        if x in res:
            res[x] += 1
        else:
            res[x] = 1
    return res

# Factorial
fact = {0: 1}
def factorial(n):
    if dynamic_factorial:
        if n not in fact:
            fact[n] = factorial(n-1) * n
        return fact[n]
    else:
        res = 1
        while n > 0:
            res = (res * n) % mod
            n -= 1
        return res

# Sum of array
def sum_of(a):
    res = 0
    for x in a:
        res = (res + x) % mod
    return res

# Prod of array
def prod_of(a):
    res = 1
    for x in a:
        res = (res * x) % mod
    return res

# End

def test():
    n = get()[0]
    a = sorted(get())
    
    i = 0
    j = n-1

    best = []
    while i < 5 and j >= n-5 and i <= j:
        if i == j:
            best.append(a[i])
        else:
            best.append(a[i])
            best.append(a[j])
        i += 1
        j -= 1

    n = len(best)
    ans = a[0] * a[1] * a[2] * a[3] * a[4]
    i = 0
    while i < n:
        j = i + 1
        while j < n:
            k = j + 1
            while k < n:
                l = k + 1
                while l < n:
                    m = l + 1
                    while m < n:
                        ans = max(ans, best[i] * best[j] * best[k] * best[l] * best[m])
                        m += 1
                    l += 1
                k += 1
            j += 1
        i += 1

    
    print(ans)

main(cases)