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 java.io.*;

import java.util.*;


public class Main {


    public static void main(String[] args) throws IOException {

        Scanner s = new Scanner(System.in);
        int t = s.nextInt();

        while(t--!=0){
            int n = s.nextInt(),pos=0,neg=0,zeros=0;
            ArrayList<Long>positives = new ArrayList<>();
            ArrayList<Long>negatives = new ArrayList<>();
            long arr[] = new long[n];
            for(int i=0;i<n;i++){
                arr[i]=s.nextInt();
                if(arr[i]>0){
                    pos++;
                    positives.add(arr[i]);

                }
                else if(arr[i]==0){
                    zeros++;
                }
                else {
                    neg++;
                    negatives.add(arr[i]);
                }

            }

            Collections.sort(positives);Collections.sort(negatives);

            long mult = 1;

            if(pos==0){
                if(zeros==0){
                    for(int i=neg-1,j=0;j<5;i--,j++){
                        mult*=negatives.get(i);
                    }
                    System.out.println(mult);
                }
                else System.out.println(0);
            }

            else if(neg==0){
                if(pos<5) System.out.println(0);
                else{
                    for(int i=pos-1,j=0;j<5;i--,j++){
                        mult*=positives.get(i);
                    }
                    System.out.println(mult);
                }
            }

            else {

                long max = Long.MIN_VALUE;

                if(pos+neg<5){
                    max = 0;
                }

                else if(pos+neg==5){
                    mult = 1;
                    for(int i=0;i<pos;i++)mult*=positives.get(i);
                    for(int i=0;i<neg;i++)mult*=negatives.get(i);

                    max = Math.max(max,mult);

                }

                else {

                    mult = 1;
                    maximo = Long.MIN_VALUE;

                    ArrayList<Long> grb = new ArrayList<>();

                    if (neg == 1) {

                        for (int i = pos - 1, j = 0; j < 5; i--, j++) mult *= positives.get(i);
                        max = Math.max(max, mult);
                    }

                    else if (neg == 2) {

                        for (int i = 0; i < 2; i++) grb.add(negatives.get(i));
                        int min = Math.min(5, pos);
                        for (int i = pos - 1, j = 0; j < min; i--, j++) grb.add(positives.get(i));
                        algo(grb, 0, 1, 0);
                        max = Math.max(max, maximo);

                    }

                    else if (neg == 3) {

                        for (int i = 0; i < 3; i++) grb.add(negatives.get(i));
                        int min = Math.min(5, pos);
                        for (int i = pos - 1, j = 0; j < min; i--, j++) grb.add(positives.get(i));
                        algo(grb, 0, 1, 0);
                        max = Math.max(max, maximo);

                    }

                    else {
                        for (int i = 0; i < 4; i++) grb.add(negatives.get(i));
                        int min = Math.min(5, pos);
                        for (int i = pos - 1, j = 0; j < min; i--, j++) grb.add(positives.get(i));
                        algo(grb, 0, 1, 0);
                        max = Math.max(max, maximo);
                    }

                }

                    if(max<0){
                        if(zeros==0) System.out.println(max);
                        else System.out.println(0);
                    }
                    else System.out.println(max);

            }
        }
    }

    static Long maximo = Long.MIN_VALUE;

    public static void algo(ArrayList<Long>arr,int sum,long prod,int i){
        if(sum==arr.size()){

            if(i==5) maximo = Math.max(maximo,prod);

        }
        else{
            algo(arr,sum+1,prod,i);
            algo(arr,sum+1,prod*arr.get(sum),i+1);
        }
    }



}




class Scanner
{
    StringTokenizer st;
    BufferedReader br;

    public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

    public String next() throws IOException
    {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public int nextInt() throws IOException {return Integer.parseInt(next());}

    public long nextLong() throws IOException {return Long.parseLong(next());}

    public String nextLine() throws IOException {return br.readLine();}

    public double nextDouble() throws IOException
    {
        String x = next();
        StringBuilder sb = new StringBuilder("0");
        double res = 0, f = 1;
        boolean dec = false, neg = false;
        int start = 0;
        if(x.charAt(0) == '-')
        {
            neg = true;
            start++;
        }
        for(int i = start; i < x.length(); i++)
            if(x.charAt(i) == '.')
            {
                res = Long.parseLong(sb.toString());
                sb = new StringBuilder("0");
                dec = true;
            }
            else
            {
                sb.append(x.charAt(i));
                if(dec)
                    f *= 10;
            }
        res += Long.parseLong(sb.toString()) / f;
        return res * (neg?-1:1);
    }

    public boolean ready() throws IOException {return br.ready();}


}