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 ans(a, n):
    pos=0
    neg=0
    p = []
    n = []
    zeroes=0
    for i in a:
        if i>0:
            pos+=1
            p.append(i)
        elif i<0:
            neg+=1
            n.append(i)

        else:
            zeroes+=1
    n.sort()
    p.sort(reverse=True)

    #case 1 : 5 positives
    pro1 = 1
    if pos<5:
        pro1 = -3001**5
        
    else:
        for i in range(5):
            pro1*=p[i]

    #case 2 : 5 negatives
    pro2 = 1
    if neg<5:
            pro2 =-3001**5
            
    else:
        for i in range(5):
            pro2*=n[-(i+1)]
            
    
    #case 3 : 1 positive, 4 negatives 
    pro3 = 1
    if neg<4:
            pro3 = -3001**5
        
    else:    
        for i in range(4):
            pro3*=n[i]

    if pos==0:
        pro3 = -3001**5

    else:
        pro3 *= p[0]

    #case 4 : 4 positives, 1 negatives 
    pro4 = 1
    if pos<4:
            pro4 = -3001**5
           
    else:
        for i in range(4):
            pro4*=p[-(i+1)]

    if neg==0:
        pro4 = -3001**5

    else:
        if pos>=4:
            pro4 *= n[-1]
    
    #case 5 : 3 positive, 2 negatives 
    pro5 = 1
    if neg<2:
        pro5 = -3001**5
        
    else:
        for i in range(2):
            pro5*=n[i]

    if pos<3:
        pro5 = -3001**5

    else:
        pro5 *= (p[0]*p[1]*p[2])

    #case 6 : 2 positive, 3 negatives 
    pro6 = 1
    if neg<3:
        pro6 = -3001**5
        
    else:        
        for i in range(3):
            pro6*=n[-(i+1)]

    if pos<=1:
        pro6 = -3001**5

    else:
        if neg>=3:
            pro6 *= (p[-1]*p[-2])
        
    if zeroes==0:
        return(max(pro1,pro2,pro3,pro4,pro5,pro6))
        
    
    else:
        return(max(0,pro1,pro2,pro3,pro4,pro5,pro6))
    

m = int(input())

for j in range(m):
    n = int(input())
    arr = input().split()

    a = []
    for i in arr:
        a.append(int(i))

    print(ans(a, n))
