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
# sys.setrecursionlimit(10**6) 
from itertools import product
def all_repeat(str1, rno):
  chars = list(str1)
  results = []
  for c in product(chars, repeat = rno):
    results.append(c)
  return results


input=sys.stdin.readline
t=int(input())
for t1 in range(t):
    n=int(input())
    l=list(map(int,input().split(" ")))
    neg=[]
    pos=[]
    zero=[]
    c=all_repeat("01",5)
    ans=-10**20
    for i in range(n):
        if(l[i]<0):
            neg.append(l[i])
        else:
            pos.append(l[i])
    neg.sort()
    pos.sort()
    neg=neg[::-1]
    # pos=pos[::-1]
    pn=len(neg)-1
    pp=len(pos)-1
    # print(c)
    # print(len(c))
    for i in range(len(c)):
        z=c[i]
        nn=pn
        np=pp
        curr=1
        # print(z,nn,np)
        f=0
        fl=0
        cn=0
        for j in range(len(z)):
            if(z[j]=='0'):
                cn+=1
        if(cn%2!=0):
            fl=1
            nn=0
            np=0
        for j in range(len(z)):
            # print(z[j])
            if(z[j]=='0'):
                if(fl==1):
                    if(nn<len(neg)):
                        curr*=neg[nn]
                        
                        nn+=1
                    else:
                        f=1
                else:
                    if(nn>-1):
                        curr*=neg[nn]
                        
                        nn-=1
                    else:
                        f=1
                # print("lol")
            else:
                if(fl==1):
                    if(np<len(pos)):
                        curr*=pos[np]
                        
                        np+=1
                    else:
                        f=1
                else:
                    if(np>-1):
                        curr*=pos[np]
                        np-=1
                    else:
                        f=1
        if(f==0):
            # print(curr)
            ans=max(ans,curr)
    # print(" aaa")
    print(ans)



    