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.util.*;
    import java.io.*;
    import java.math.*;
     
    public class Main {
        static PrintWriter out;
        static Reader in;
        public static void main(String[] args) throws IOException {
            //out = new PrintWriter(new File("out.txt"));
            //PrintWriter out = new PrintWriter(System.out);
            //in = new Reader(new FileInputStream("in.txt"));
            //Reader in = new Reader();
            input_output();
            Main solver = new Main();
            solver.solve();
            out.flush();
            out.close();
     
        }
     
        static long INF = (long)1e16;
        static int maxn = (int)1e6+1000;
        static int mod=(int)1e9+7 ;
        static int n, m, q, k, t;
     

        void solve() throws IOException{
            
            t = in.nextInt();

            while (t --> 0) {
                n = in.nextInt();

                long[] arr = new long[n];
                ArrayList<Long> neg = new ArrayList<>(),
                                pos = new ArrayList<>();
                int zero = 0;
                for (int i = 0; i < n; i++) {
                    arr[i] = in.nextLong();
                    if (arr[i] < 0) neg.add(arr[i]);
                    else if (arr[i] > 0) pos.add(arr[i]);
                    else zero++;
                }

                Collections.sort(neg);
                Collections.sort(pos);

                boolean positive = false;
                if (pos.size() >= 5) positive = true;
                if (pos.size() >= 3 && neg.size() >= 2) positive = true;
                if (pos.size() >= 1 && neg.size() >= 4) positive = true;

                if (!positive) {
                    if (zero != 0) {
                        out.println(0);
                        continue;
                    } else {
                        long ans = 1;
                        Arrays.sort(arr);
                        for (int i = n-1; i >= n-5; i--) ans *= arr[i];
                        out.println(ans);
                        continue;
                    }
                } else {
                    long ans = 1, tmp = 1;
                    if (pos.size() >= 5) {
                        for (int i = pos.size()-1; i >= pos.size()-5; i--) tmp *= pos.get(i);
                        ans = Math.max(ans, tmp);
                    }

                    tmp = 1;
                    if (pos.size() >= 3 && neg.size() >= 2) {
                        for (int i = pos.size()-1; i >= pos.size()-3; i--) tmp *= pos.get(i);
                        for (int i = 0; i <= 1; i++) tmp *= neg.get(i);
                        ans = Math.max(ans, tmp);
                    }
                    tmp = 1;
                    if (pos.size() >= 1 && neg.size() >= 4) {
                        for (int i = pos.size()-1; i >= pos.size()-1; i--) tmp *= pos.get(i);
                        for (int i = 0; i <= 3; i++) tmp *= neg.get(i);
                        ans = Math.max(ans, tmp);
                    }
                    out.println(ans);
                }
            }

        }
     
        //<>
     
        static class Reader {
     
            private InputStream mIs;
            private byte[] buf = new byte[1024];
            private int curChar;
            private int numChars;
        
            public Reader() {
                this(System.in);
            }
        
            public Reader(InputStream is) {
                mIs = is;
            }
        
            public int read() {
                if (numChars == -1) {
                    throw new InputMismatchException();
        
            }
                if (curChar >= numChars) {
                    curChar = 0;
                    try {
                        numChars = mIs.read(buf);
                    } catch (IOException e) {
                        throw new InputMismatchException();
                    }
                    if (numChars <= 0) {
                        return -1;
                    }
                }
                return buf[curChar++];
            }
        
            public String nextLine() {
                int c = read();
                while (isSpaceChar(c)) {
                    c = read();
                }
                StringBuilder res = new StringBuilder();
                do {
                    res.appendCodePoint(c);
                    c = read();
                } while (!isEndOfLine(c));
                return res.toString();
            }
        
            public String next() {
                int c = read();
                while (isSpaceChar(c)) {
                    c = read();
                }
                StringBuilder res = new StringBuilder();
                do {
                    res.appendCodePoint(c);
                    c = read();
                } while (!isSpaceChar(c));
                return res.toString();
            }
        
            double nextDouble()
            {
                return Double.parseDouble(next());
            }
        
            public long nextLong() {
                int c = read();
                while (isSpaceChar(c)) {
                    c = read();
                }
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = read();
                }
                long res = 0;
                do {
                    if (c < '0' || c > '9') {
                        throw new InputMismatchException();
                    }
                    res *= 10;
                    res += c - '0';
                    c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
            }
        
            public int nextInt() {
                int c = read();
                while (isSpaceChar(c)) {
                    c = read();
                }
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = read();
                }
                int res = 0;
                do {
                    if (c < '0' || c > '9') {
                        throw new InputMismatchException();
                    }
                    res *= 10;
                    res += c - '0';
                    c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
            }
        
            public boolean isSpaceChar(int c) {
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
            }
        
            public boolean isEndOfLine(int c) {
                return c == '\n' || c == '\r' || c == -1;
            }
     
        }
        static void input_output() throws IOException {
            File f = new File("in.txt");
            if(f.exists() && !f.isDirectory()) { 
                in = new Reader(new FileInputStream("in.txt"));
            } else in = new Reader();
            f = new File("out.txt");
            if(f.exists() && !f.isDirectory()) {
                out = new PrintWriter(new File("out.txt"));
            } else out = new PrintWriter(System.out);
        }
    }