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 my_func(d):
    p_max = p1 = p2 = p3 = p4 = d[0] * d[1] * d[2] * d[3] * d[4]
    pol = []
    otr = []
    kol_nul = 0
    for i in d:
        if i > 0:
            pol.append(i)
        elif i < 0:
            otr.append(i)
        else:
            kol_nul += 1

    # положительные сортируем по убыванию
    pol_sort = sorted(pol, reverse=True)
    # otr sort по убыванию модуля
    otr_sort = sorted(otr)

    if len(pol) >= 5:
        # посчитаем произведение 5 максиамльных положительных чисел
        p1 = pol_sort[0] * pol_sort[1] * pol_sort[2] * pol_sort[3] * pol_sort[4]
    if len(pol) >= 3 and len(otr) >= 2:
        # посчитаем произведение 3 максимальных положительных и 2 максимальных по модулю отрицательных чисел
        p2 = pol_sort[0] * pol_sort[1] * pol_sort[2] * otr_sort[0] * otr_sort[1]
    if len(pol) >= 1 and len(otr) >= 4:
        # посчитаем произведение 1 максимального положительного и 4 максимальных по модулю отрицательных числел
        p3 = pol_sort[0] * otr_sort[0] * otr_sort[1] * otr_sort[2] * otr_sort[3]
    if len(pol) == 0 and len(otr) >= 5:
        # otr_sort[-1] - последний элемент наименьший по модулю
        p4 = otr_sort[-1] * otr_sort[-2] * otr_sort[-3] * otr_sort[-4] * otr_sort[-5]
    p_max = max(p_max, p1, p2, p3, p4)
    if kol_nul > 0:
        p_max = max(p_max, 0)
    return p_max


a = []
k = int(input())
for i in range(k):
    int(input())
    d = list(map(int, input().split()))
    a.append(my_func(d))
for i in range(k):
    print(a[i])


# есть 5 положительных (+) p1
# есть 3 положительных и 2 отрицательных (+) p2
# есть одно положительное и 4 отрицательных (+) p3
# только отрицательные -> берем 5 меньших по модулю (-) p4
# четное количество положительных, остальные отрицательные и 0 -> результат 0 (+)

# всего 5 элементов:
# четное количество положительных, остальные отрицательные (+) p_max

