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.
######################################################
############Created by Devesh Kumar###################
#############devesh1102@gmail.com####################
##########For CodeForces(Devesh1102)#################
#####################2020#############################
######################################################
import sys
input = sys.stdin.readline
 
import sys 
import heapq 
import copy
import math
import decimal
 
# import sys.stdout.flush as flush
# from decimal import *
#heapq.heapify(li) 
#
#heapq.heappush(li,4) 
#
#heapq.heappop(li)
#
# &    Bitwise AND Operator    10 & 7 = 2
# |    Bitwise OR Operator    10 | 7 = 15
# ^    Bitwise XOR Operator    10 ^ 7 = 13
 
# <<    Bitwise Left Shift operator    10<<2 = 40
# >>    Bitwise Right Shift Operator
# '''############ ---- Input Functions ---- #######Start#####'''
# n = 100
# parent = [-1 for i in range(n)]
# def find(a):
#     if parent[a] == a:
#         return a
#     else:
#         parent[a] = find(parent[a])
    
# def union(a,b):








    # print(lsp )
def inp():
    return(int(input()))
def inlt(): 
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def insr2():
    s = input()
    s = list(s[:len(s) - 1])
    s = [ord(s[i]) - ord("a") for i in range(len(s))]
    return s
def invr():
    return(map(int,input().split()))
############ ---- Input Functions ---- #######End
# #####   


ans = 0
def pr_list(a):
    print( *a , sep=" ")

def swap(a,b):
    temp = a
    a = b
    b = temp
    return [ a,b]
    # return [b,a]
def pri(a,b):
    s = "? " + str(a) + " " + str(b)
    print(s)
    sys.stdout.flush()
def main():
    tests =  inp()
    # tests = 1
    mod = 1000000007
    limit = 10**18
    ans = 0
    stack = []
    hashm = {}
    arr = []
    heapq.heapify(arr) 
    def find_next(hashm,itr):
        for i in range(itr,len(hashm)):
            if hashm[i] == 0:
                return i 

    for test in range(tests):
        n= inp()
        arr= inlt()
        pos = [[0 for i in range(n)] for k in range(5)]
        neg = [[0 for i in range(n)] for k in range(5)]
        pos[0][0] = arr[0]
        neg[0][0] = arr[0]
        for i in range(1,n):
            pos[0][i] = max(arr[i],pos[0][i-1])
            neg[0][i] = min( arr[i], neg[0][i-1])
        for k in range(1,5):
            pos[k][k] = max( arr[k] * pos[k-1][k-1], arr[k] * neg[k-1][k-1])
            neg[k][k] = min( arr[k] * pos[k-1][k-1], arr[k] * neg[k-1][k-1]) 
            for i in range(k+1,n):
                pos[k][i] = max(pos[k][i-1], arr[i] * pos[k-1][i-1],  arr[i] * neg[k-1][i-1])
                neg[k][i] = min(neg[k][i-1],  arr[i] * pos[k-1][i-1],  arr[i] * neg[k-1][i-1])
        ans = pos[4][4]
        # print(pos)
        # print(neg)
        for i in range(4,n):
            ans= max(ans, pos[4][i])
        print(ans)


            
                

        


if __name__== "__main__":
    main()
