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.*;
public class MainClass
{
    public static void main(String[] args) throws IOException
    {
        Reader in = new Reader();
        int t = in.nextInt();
        StringBuilder stringBuilder = new StringBuilder();
        while (t-- > 0)
        {
            int n = in.nextInt();
            ArrayList<Long> pos = new ArrayList<>();
            ArrayList<Long> neg = new ArrayList<>();
            for (int i=0;i<n;i++)
            {
                long x = in.nextLong();
                if (x >= 0L)
                    pos.add(x);
                else
                    neg.add(x);
            }
            Collections.sort(pos, Collections.reverseOrder());
            Collections.sort(neg);
            long ans = Long.MIN_VALUE;
            if (pos.size() >= 5)
            {
                long pp = 1L;
                for (int i=0;i<5;i++)
                    pp *= pos.get(i);
                ans = Math.max(ans, pp);
            }
            if (neg.size() >= 2 && pos.size() >= 3)
            {
                long pp = 1L;
                for (int i=0;i<3;i++)
                    pp *= pos.get(i);
                for (int i=0;i<2;i++)
                    pp *= neg.get(i);
                ans = Math.max(ans, pp);
            }
            if (neg.size() >= 4 && pos.size() >= 1)
            {
                long pp = 1L;
                for (int i=0;i<1;i++)
                    pp *= pos.get(i);
                for (int i=0;i<4;i++)
                    pp *= neg.get(i);
                ans = Math.max(ans, pp);
            }
            Collections.sort(pos);
            Collections.sort(neg, Collections.reverseOrder());
            if (neg.size() >= 5)
            {
                long pp = 1L;
                for (int i=0;i<5;i++)
                    pp *= neg.get(i);
                ans = Math.max(ans, pp);
            }
            if (pos.size() >= 2 && neg.size() >= 3)
            {
                long pp = 1L;
                for (int i=0;i<3;i++)
                    pp *= neg.get(i);
                for (int i=0;i<2;i++)
                    pp *= pos.get(i);
                ans = Math.max(ans, pp);
            }
            if (pos.size() >= 4 && neg.size() >= 1)
            {
                long pp = 1L;
                for (int i=0;i<1;i++)
                    pp *= neg.get(i);
                for (int i=0;i<4;i++)
                    pp *= pos.get(i);
                ans = Math.max(ans, pp);
            }
            stringBuilder.append(ans).append("\n");
        }
        System.out.println(stringBuilder);
    }
}
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')
                break;
            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();
    }
}
