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.sql.SQLSyntaxErrorException;
import java.util.*;
import java.io.*;
import java.util.stream.StreamSupport;


public class Solution {
    static long mod = (long)Math.pow(10,9)+7l;
    public static void main(String str[]) throws IOException {
        Reader sc = new Reader();
        BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
//        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-->0){
            int n = sc.nextInt();
            if(n==5){
                long ans =1;
                for(int i=0;i<5;i++)    ans*=sc.nextInt();
                System.out.println(ans);
                continue;
            }
            int[] arr = new int[n];
            for(int i=0;i<n;i++){
                arr[i] = sc.nextInt();
            }
            Arrays.sort(arr);
            ArrayList<Integer> ps = new ArrayList<>();
            ArrayList<Integer> ns = new ArrayList<>();
            ArrayList<Integer> two = new ArrayList<>();
//            ArrayList<Integer> ntwo = new ArrayList<>();
//            ArrayList<Integer> ptwo = new ArrayList<>();
            for(int i=0;i<4;i+=2){
                if(i<n-1 && arr[i]<=0 && arr[i+1]<=0){
                    two.add(arr[i]*arr[i+1]);
//                    ntwo.add(arr[i]*arr[i+1]);
                }
            }

            for(int i=0;i<n;i++){
                if(arr[i]<=0)   ns.add(arr[i]);
                else    ps.add(arr[i]);
            }
            for(int i=n-2;i>n-6;i-=2){
                if(i>0 && arr[i]>0 && arr[i-1]>0){
                    two.add(arr[i]*arr[i-1]);
//                    ptwo.add(arr[i]*arr[i-1]);
                }
            }
            long ans =1;
            if(ps.size()<1){
                for(int i=n-1;i>=n-5;i--){
                    ans*=arr[i];
                }
            }
            else{
                Collections.sort(two,Collections.reverseOrder());
                for (int i = 0; i < two.size() && i < 2; i++) {
                    ans *= two.get(i);
                }
                ans*=arr[n-1];
            }
            System.out.println(ans);


        }
        output.flush();
    }

    static long treeTraversal(Tree arr[], int parent, int x){
        long tot = 0;
        for(int i: arr[x].al){
            if(i!=parent){
                tot+=treeTraversal(arr, x, i);
            }
        }
        arr[x].child = tot;
        if(arr[x].child==0) arr[x].child = 1;
        return tot+1;
    }

    public static int primeFactors(int n, int k)
    {
        int ans = 0;
        while (n%2==0)
        {
            ans++;
            if(ans>=k)  return k;
            n /= 2;
        }
        for (int i = 3; i <= Math.sqrt(n); i+= 2)
        {
            while (n%i == 0)
            {
                ans++;
                n /= i;
                if(ans>=k)  return k;
            }
        }

        if (n > 2)  ans++;
        return ans;
    }
    static int binaryLow(ArrayList<Integer> arr, int x, int s, int e){
        if(s>=e){
            if(arr.get(s)>=x)  return s;
            else    return s+1;
        }
        int m = (s+e)/2;
        if(arr.get(m)==x)  return m;
        if(arr.get(m)>x)   return binaryLow(arr,x,s,m);
        if(arr.get(m)<x)   return binaryLow(arr,x,m+1,e);
        return 0;
    }
    static int binaryLow(int[] arr, int x, int s, int e){
        if(s>=e){
            if(arr[s]>=x)  return s;
            else    return s+1;
        }
        int m = (s+e)/2;
        if(arr[m]==x)  return m;
        if(arr[m]>x)   return binaryLow(arr,x,s,m);
        if(arr[m]<x)   return binaryLow(arr,x,m+1,e);
        return 0;
    }
    static int binaryHigh(int[] arr, int x, int s, int e){
        if(s>=e){
            if(arr[s]<=x)  return s;
            else    return s-1;
        }
        int m = (s+e)/2;
        if(arr[m]==x)  return m;
        if(arr[m]>x)   return binaryHigh(arr,x,s,m-1);
        if(arr[m]<x)   return binaryHigh(arr,x,m+1,e);
        return 0;
    }


    static void arri(int arr[], int n, Reader sc) throws IOException{
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
    }
    static void arrl(long arr[], int n, Reader sc) throws IOException{
        for(int i=0;i<n;i++){
            arr[i] = sc.nextLong();
        }
    }

    static long gcd(long a, long b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
    static long power(long x, long y, long p)
    {
        long res = 1; // Initialize result

        x = x % p; // Update x if it is more than or
        // equal to p

        if (x == 0)
            return 0; // In case x is divisible by p;

        while (y > 0)
        {

            // If y is odd, multiply x with result
            if ((y & 1) != 0)
                res = (res * x) % p;

            // y must be even now
            y = y >> 1; // y = y/2
            x = (x * x) % p;
        }
        return res;
    }

//    static boolean dfs(Tree node, boolean[] visited, int parent, ArrayList<Tree> tt){
//        visited[node.a] = true;
//        boolean b = false;
//        for(int i: node.al){
//            if(tt.get(i).a!=parent){
//                if(visited[tt.get(i).a])    return true;
//                b|= dfs(tt.get(i), visited, node.a, tt);
//            }
//        }
//        return b;
//    }


    static class Pair{
        //        int ind;
        long a;
        long b;
        //        ArrayList<Integer> ii = new ArrayList<>();
        Pair( long a, long b){
//            this.ind = i;
            this.a = a;
            this.b = b;
        }

    }
    static class SortbyI implements Comparator<Pair> {
        // Used for sorting in ascending order of
        // roll number
        public int compare(Pair a, Pair b)
        {
            if(a.b>=b.b) return 1;
            else return -1;
        }
    }
    //    static class SortbyD implements Comparator<Pair> {
//        // Used for sorting in ascending order of
//        // roll number
//        public int compare(Pair a, Pair b)
//        {
//            return b.a - a.a;
//        }
//    }
    static int binarySearch(ArrayList<Pair> a, int x, int s, int e){
        if(s>=e){
            if(x<=a.get(s).b)  return s;
            else    return s+1;
        }
        int mid = (e+s)/2;
        if(a.get(mid).b<x){
            return binarySearch(a, x, mid+1, e);
        }
        else    return binarySearch(a,x,s, mid);
    }

    //    static class Edge{
//        int a;
//        int b;
//        int c;
//        int sec;
//        Edge(int a, int b, int c, int sec){
//            this.a = a;
//            this.b = b;
//            this.c = c;
//            this.sec = sec;
//        }
//
//    }
    static class Tree{
        int a;
        ArrayList<Integer> al = new ArrayList<>();
        long curr = 0;
        long freeSpace = 0;
        long child = 0;
        long max =0;
        Tree(int a){
            this.a = a;
        }

    }
    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(
                    new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    if (cnt != 0) {
                        break;
                    }
                    else {
                        continue;
                    }
                }
                buf[cnt++] = (byte)c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0,
                    BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }


    static boolean isPrime(int n)
    {
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
        if (n % 2 == 0 ||
                n % 3 == 0)
            return false;

        for (int i = 5;
             i * i <= n; i = i + 6)
            if (n % i == 0 ||
                    n % (i + 2) == 0)
                return false;

        return true;
    }
    static ArrayList<Integer> sieveOfEratosthenes(int n)
    {
        ArrayList<Integer> al = new ArrayList<>();
        // Create a boolean array
        // "prime[0..n]" and
        // initialize all entries
        // it as true. A value in
        // prime[i] will finally be
        // false if i is Not a
        // prime, else true.
        boolean prime[] = new boolean[n + 1];
        for (int i = 0; i <= n; i++)
            prime[i] = true;

        for (int p = 2; p * p <= n; p++)
        {
            // If prime[p] is not changed, then it is a
            // prime
            if (prime[p] == true)
            {
                // Update all multiples of p
                for (int i = p * p; i <= n; i += p)
                    prime[i] = false;
            }
        }

        // Print all prime numbers
        for (int i = 2; i <= n; i++)
        {
            if (prime[i] == true)
                al.add(i);
        }
        return al;
    }

}





