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{
	
	int t = sc.nextInt();
	while (t-->0){
		int n = sc.nextInt();
		long first = 1;
		int count = 0;
		ArrayList<Long> pos = new ArrayList<Long>();
		ArrayList<Long> neg = new ArrayList<Long>();
		boolean hasZero = false;
		for (int i = 0; i < n; i++) {
			long x = sc.nextInt();
			if (x == 0) hasZero = true;
			else if (x > 0) pos.add(x);
			else neg.add(x);
			if (count < 5) {
				first *= x;
				count++;
			}
		}
		Collections.sort(pos);
		Collections.sort(neg); // reverse of pos
		List<Long> sol = new ArrayList<Long>();
		if (hasZero) sol.add((long)0);
		
		int ps = pos.size();
		int ns = neg.size();
		
		if (pos.size() >= 5){
			long s = 1;
			int i = ps-1;
			int cp = 0;
			while (cp < 5) {
				s *= pos.get(i);
				i--;
				cp++;
			}
			sol.add(s);
		}
		if (pos.size() >= 3 && neg.size() >= 2) {
			long s = 1;
			int i = ps-1;
			int cp = 0;
			while (cp < 3) {
				s *= pos.get(i);
				i--;
				cp++;
			}
			
			for (int j = 0; j < 2; j++) {
				s *= neg.get(j);
			}
			sol.add(s);
		}
		if (pos.size() >= 1 && neg.size() >= 4) {
			long s = 1;
			int i = ps-1;
			int cp = 0;
			while (cp < 1) {
				s *= pos.get(i);
				i--;
				cp++;
			}
			for (int j = 0; j < 4; j++) {
				s *= neg.get(j);
			}
			sol.add(s);
		}
		
		if (neg.size() >= 5) {
			long s = 1;
			int i = ns - 1;
			int cn = 0;
			while (cn < 5) {
				s *= neg.get(i);
				cn++;
				i--;
			}
			sol.add(s);
		}
		if (neg.size() >= 3 && pos.size() >= 2) {
			long s = 1;
			int i = ns - 1;
			int cn = 0;
			while (cn < 3) {
				s *= neg.get(i);
				cn++;
				i--;
			}
			for (int j = 0; j < 2; j++) s *= pos.get(j);
			sol.add(s);

		}
		if (neg.size() >= 1 && pos.size() >= 4) {
			long s = 1;
			int i = ns - 1;
			int cn = 0;
			while (cn < 1) {
				s *= neg.get(i);
				cn++;
				i--;
			}
			for (int j = 0; j < 4; j++) s *= pos.get(j);
			sol.add(s);

		}
		
		sol.add(first);
		Collections.sort(sol);
		out.println(sol.get(sol.size()-1));
		
	}
	
	out.close();
   }
   
  
   static long powMod(long base, long exp, long mod) {
	   if (base == 0 || base == 1) return base;
	   if (exp == 0) return 1;
	   if (exp == 1) return base % mod;
	   long R = powMod(base, exp/2, mod) % mod;
	   R *= R;
	   R %= mod;
	   if ((exp & 1) == 1) {
		   return base * R % mod;
	   }
	   else return R % mod;
   }
   
   static long pow(long base, long exp) {
	   if (base == 0 || base == 1) return base;
	   if (exp == 0) return 1;
	   if (exp == 1) return base;
	   long R = pow(base, exp/2);
	   if ((exp & 1) == 1) {
		   return R * R * base;
	   }
	   else return R * R;
   }
   

   
   
   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') 
                   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(); 
       } 
   }

	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	public static Reader sc = new Reader();
}











