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 Whiplash99
import java.io.*;
import java.util.*;
public class B
{
    private static void shuffleArray(long[] arr)
    {
        int n = arr.length;
        Random rnd = new Random();
        for(int i=0; i<n; ++i)
        {
            long tmp = arr[i];
            int randomPos = i + rnd.nextInt(n-i);
            arr[i] = arr[randomPos];
            arr[randomPos] = tmp;
        }
    }
    public static void main(String[] args) throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        int i,N;

        int T=Integer.parseInt(br.readLine().trim());
        StringBuilder sb=new StringBuilder();

        while(T-->0)
        {
            N=Integer.parseInt(br.readLine().trim());
            String[] s=br.readLine().trim().split(" ");
            long a[]=new long[N];
            for(i=0;i<N;i++) a[i]=Integer.parseInt(s[i]);

            ArrayList<Long> pos=new ArrayList<>();
            ArrayList<Long> neg=new ArrayList<>();

            shuffleArray(a);
            Arrays.sort(a);

            for(i=0;i<5;i++) neg.add(a[i]);
            for(i=N-1;i>N-6;i--) pos.add(a[i]);

            long prod=1,tmp=1;
            for(long k:pos) prod*=k;

            tmp*=neg.get(0)*neg.get(1);
            tmp*=pos.get(0)*pos.get(1)*pos.get(2);
            prod=Math.max(prod,tmp);

            tmp=neg.get(0)*neg.get(1)*neg.get(2)*neg.get(3)*pos.get(0);
            prod=Math.max(prod,tmp);

            sb.append(prod).append("\n");
        }
        System.out.println(sb);
    }
}