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.
class Node():
    def __init__(self,val):
        self.val=val
        self.children=None
        self.centroid=None
        self.edges=[]

class Graph():
    def __init__(self):
        self.root=None
    def add_edge(self,a,b):
        if(self.root==None):
            self.root=a
        a.edges.append(b)
        b.edges.append(a)



def dfs_children(g,root,visited):
    visited.add(root.val)
    c=0
    for i in root.edges:
        if(i.val not in visited):
            visited.add(i.val)
            c+=1+dfs_children(g,i,visited)
    root.children=c
    return root.children




def dfs_centroids(g,root,visited,n,ce):
    visited.add(root.val)
    c=-1
    t=0
    for i in root.edges:
        if(i.val not in visited):
            visited.add(i.val)
            c=max(c,i.children+1)
            dfs_centroids(g,i,visited,n,ce)
            t+=i.children+1
    c=max(c,n-t-1)
    root.centroid=c
    if(c in ce):
        ce[c].append(root)
    else:
        ce[c]=[root]
    return root.centroid

def get_leaf(root,li,visited,noti):
    if(root.val==noti.val):
        return False
    visited.add(root.val)
    flag=True
    for i in root.edges:
        if(i.val not in visited and i.val!=noti.val):
            visited.add(i.val)
            li[0]=root
            li[1]=i
            flag=flag & get_leaf(root,li,visited,noti)
    return flag


def pro(li):
    p=1
    for i in li:
        p*=i
    return p


def process():
    n=int(input())
    li=list(map(int,input().split()))
    ans=[]
    s1=list(li)
    s2=list(li)
    s1.sort()
    s2.sort(reverse=True)
    ans.append(pro(s1[:5]))
    ans.append(pro(s1[:4])*s2[0])
    ans.append(pro(s1[:3]) * pro(s2[:2]))
    ans.append(pro(s1[:2])*pro(s2[:3]))
    ans.append(pro(s1[:1]) * pro(s2[:4]))
    ans.append(pro(s2[:5]))
    print(max(ans))


    # g=Graph()
    # nodes={}
    # for i in range(n-1):
    #     if(a not in nodes):
    #         nodes[a]=Node(a)
    #     if(b not in nodes):
    #         nodes[b]=Node(b)
    #     g.add_edge(nodes[a],nodes[b])
    # visited=set()
    # dfs_children(g,g.root,visited)
    # visited=set()
    # ce={}
    # dfs_centroids(g,g.root,visited,n,ce)
    # centroid=min(list(ce.keys()))
    # if(len(ce[centroid])==1):
    #     print(g.root.val,g.root.edges[0].val)
    #     print(g.root.val, g.root.edges[0].val)
    #     pass
    # else:
    #     li=[-1,ce[centroid][0]]
    #     # print(li[1].val)
    #     for i in ce[centroid][0].edges:
    #         visited={i.val,ce[centroid][0].val}
    #         li[0]=ce[centroid][0]
    #         li[1]=i
    #         if(get_leaf(i,li,visited,ce[centroid][1])):
    #             break
    #
    #     print(li[0].val,li[1].val)
    #     print(li[1].val,ce[centroid][1].val)
    #     a,b=list(map(int,input().split()))




tests=int(input())
for i in range(tests):
    process()