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.math.BigInteger;
	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Collection;
	import java.util.Collections;
	import java.util.Comparator;
	import java.util.HashMap;
	import java.util.InputMismatchException;
	import java.util.Iterator;
	import java.util.LinkedHashSet;
	import java.util.LinkedList;
	import java.util.List;
	import java.util.Map;
	import java.util.Map.Entry;
	import java.util.PriorityQueue;
	import java.util.Queue;
	import java.util.Scanner;
	import java.util.Set;
	import java.util.Stack;
	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStream;
	import java.io.InputStreamReader;
	import java.util.Scanner;
	import java.util.StringTokenizer;
	import java.util.TreeMap;
	import java.util.TreeSet;
	
	public class Main {
										
	//	static FastReader sc= new FastReader();
	static ArrayList<Integer> C;
	static ArrayList<Integer> B;
	static	int mod=(int)1e9+9;
	static long dp[];
	static int k;
	
	static StringBuilder as=new StringBuilder();
	static InputReader rd=new InputReader(System.in);
	
	
	public static void main(String[] args) {
		//HashMap<Long,Long>map =new HashMap<Long, Long>();
				
			//code
		    
		
			int t=rd.readInt();
			
			while(t-->0) {
			int n=rd.readInt();
			
			
			long a[]=new long[n];
			int ne=0;int p=0;
			for(int i=0;i<n;i++) {a[i]=rd.readInt();
			if(a[i]>=0)p++;
			else ne++;
			
			}
			
			
			
				
			
			
			System.out.println(maxProductSubarrayOfSizeK(a, n, 5));
			
			
			
			}

			
		}
	 static long maxProductSubarrayOfSizeK(long A[], int n, int k) 
	    { 
	        // sorting given input array 
	        Arrays.sort(A); 
	  
	        // variable to store final product of all element 
	        // of sub-sequence of size k 
	        long product = 1; 
	  
	        // CASE I 
	        // If max element is 0 and 
	        // k is odd then max product will be 0 
	        if (A[n - 1] == 0 && k % 2 != 0) 
	            return 0; 
	  
	        // CASE II 
	        // If all elements are negative and 
	        // k is odd then max product will be 
	        // product of rightmost-subarray of size k 
	        if (A[n - 1] <= 0 && k % 2 != 0) { 
	            for (int i = n - 1; i >= n - k; i--) 
	                product *= A[i]; 
	            return product; 
	        } 
	  
	        // else 
	        // i is current left pointer index 
	        int i = 0; 
	  
	        // j is current right pointer index 
	        int j = n - 1; 
	  
	        // CASE III 
	        // if k is odd and rightmost element in 
	        // sorted array is positive then it 
	        // must come in subsequence 
	        // Multiplying A[j] with product and 
	        // correspondingly changing j 
	        if (k % 2 != 0) { 
	            product *= A[j]; 
	            j--; 
	            k--; 
	        } 
	  
	        // CASE IV 
	        // Now k is even 
	        // Now we deal with pairs 
	        // Each time a pair is multiplied to product 
	        // ie.. two elements are added to subsequence each time 
	        // Effectively k becomes half 
	        // Hence, k >>= 1 means k /= 2 
	        k >>= 1; 
	  
	        // Now finding k corresponding pairs 
	        // to get maximum possible value of product 
	        for (int itr = 0; itr < k; itr++) { 
	            // product from left pointers 
	            long left_product = A[i] * A[i + 1]; 
	  
	            // product from right pointers 
	            long right_product = A[j] * A[j - 1]; 
	  
	            // Taking the max product from two choices 
	            // Correspondingly changing the pointer's position 
	            if (left_product > right_product) { 
	                product *= left_product; 
	                i += 2; 
	            } 
	            else { 
	                product *= right_product; 
	                j -= 2; 
	            } 
	        } 
	  
	        // Finally return product 
	        return product; 
	    } 
	  

	
		void BFS(int s,int n) {
			
			
			boolean visited[]= new boolean[n];
			
			LinkedList<Integer> q=new LinkedList<>();
			
			
			
			
		}
			    
			    
			    
			    
			
	
	
	
	static int MSB(int z) {
		for (int i=20; i>=0; i--) {
			if (((z>>i)&1)!=0) return i;
		}
		return -1;
	}

	
	static long ans=(long)1e18;
	static void dfs(int s,ArrayList<ArrayList<Integer>> adj,boolean []visited) {
		
		
		visited[s]=true;
		
		
		for(int i:adj.get(s)) {
			
			if(!visited[i])dfs(i, adj, visited);
		}
		
		
		
		
	}
	
	static boolean isPowerOfTwo (int x) 
	{ 
	  /* First x in the below expression is  
	    for the case when x is 0 */
	    return x!=0 && ((x&(x-1)) == 0); 
	      
	} 
	
			
			//extended Euclidean Algorithm 
			public static int gcd(int a, int b) 
			{ 
			    if (a == 0) 
			        return b; 
			      
			    return gcd(b%a, a); 
			} 
	
	
	static boolean isPrime(int n) { 
	    //check if n is a multiple of 2 
	    if (n%2==0) return false; 
	    //if not, then just check the odds 
	    for(int i=3;i<=Math.sqrt(n);i+=2) { 
	        if(n%i==0) 
	            return false; 
	    } 
	    return true; 
	} 
				static long solve(long n) {
					long sum=(n*(n+1)/2);
					long l=sum/2;
					if(n==3) {
						return 2;
					}
					long k=n;
					if(sum%2==0) {
						long j=n;
						int c=1;
						boolean flag=false;
						long s=0;
						while(j<l) {
							
							n--;
							c++;
							j+=n;
							
							if(j==l) {flag =true;s=n-1;}
							
						}
						long point =l-(j-k);
						long e=0;
						
						if(flag) {
							e=s*(s-1)/2+(k-s)*(k-s-1)/2;
							
						}
						
					//System.out.println(e+" "+c);
						return (c+e);
					}
					else return 0;
					
					
					
				
					
				}
		
		
		static class solver{
			int d;
			double w;
			public solver(int d,double w) {
				
			this.d=d;
			this.w=w;
			
				
			}
			
			
		}
		
		
		
		
		
		
		  static class InputReader {
		        private InputStream stream;
		        private byte[] buf = new byte[1024];
		        private int curChar;
		        private int numChars;
		        private SpaceCharFilter filter;
	
		        public InputReader(InputStream stream) {
		            this.stream = stream;
		        }
	
		        public int read() {
		            if (numChars == -1)
		                throw new InputMismatchException();
		            if (curChar >= numChars) {
		                curChar = 0;
		                try {
		                    numChars = stream.read(buf);
		                } catch (IOException e) {
		                    throw new InputMismatchException();
		                }
		                if (numChars <= 0)
		                    return -1;
		            }
		            return buf[curChar++];
		        }
	
		        public int readInt() {
		            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 String readString() {
	    int c = read();
	    while (isSpaceChar(c))
	        c = read();
	    StringBuilder res = new StringBuilder();
	    do {
	        res.appendCodePoint(c);
	        c = read();
	    } while (!isSpaceChar(c));
	    return res.toString();
	}
	
	public boolean isSpaceChar(int c) {
	    if (filter != null)
	        return filter.isSpaceChar(c);
	    return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		        }
	
		        public String next() {
		            return readString();
		        }
	
		    }
		
		  public interface SpaceCharFilter {
		        public boolean isSpaceChar(int ch);
		    }	
		
		
		static int c=0;
	static    void DFSUtil(int s,ArrayList<ArrayList<solver>> adj,int V,boolean visited[],double pw) {
	    	
		
	    	visited[s]=true;
	    	c++;
	    	
	  // 	System.out.print(c+" ");
	
	for(solver i:adj.get(s)) {
		
	
	if(pw>i.w) {
		//System.out.println(pw+" "+i.w+" "+(pw>i.w));
	    		continue;}
	    		
	    		if(!visited[i.d]) {
	    			
	    			DFSUtil(i.d,adj,V,visited,i.w);
	    		}
	    		
	    	}
	    	
	    }
	    
		
		public static <T> ArrayList<T> removeDuplicates(ArrayList<T> list) 
	    { 
	  
	        // Create a new LinkedHashSet 
	        Set<T> set = new LinkedHashSet<>(); 
	  
	        // Add the elements to set 
	        set.addAll(list); 
	  
	        // Clear the list 
	        list.clear(); 
	  
	        // add the elements of set 
	// with no duplicates to the list 
	        list.addAll(set); 
	  
	        // return the list 
			        return list; 
			    } 
	static		class Ungraph{
				
				
				int V,E;
				
				Edge edge[];
				
				class Edge{
					int src,dest;
					
				};
				
					public Ungraph(int v,int e) {
						// TODO Auto-generated constructor stub
	
	V=v;
	
	E=e;
	edge=new Edge[e];
	
	for(int i=0;i<e;i++) {
		edge[i]=new Edge();
		
	}
	
	
	}
	
	class subset{
		
		int parent;
		int rank;
		
	}
	
	int find(subset subsets[],int i) {
		
		if(subsets[i].parent!=i) {
			subsets[i].parent=find(subsets,subsets[i].parent);
		}
		return subsets[i].parent;
	}
	
	
	//finding union
												void Union(subset subsets[],int x,int y) {
													int xroot=find(subsets,x);
													int yroot=find(subsets,y);
													
													if(subsets[xroot].rank<subsets[yroot].rank)subsets[xroot].parent=yroot;
													if(subsets[xroot].rank<subsets[yroot].rank)subsets[yroot].parent=xroot;
													 else
													    { 
													        subsets[xroot].parent = yroot; 
													        subsets[yroot].rank++; 
													    } 
												}
												
												
												  
												
												
												int isCycle(Ungraph graph) {
													
													subset subsets[]=new subset [graph.V];
													
														for(int i=0;i<graph.V;i++) { 	
															 subsets[i] = new subset(); 
															 subsets[i].parent=i;
															 subsets[i].rank=0;
															
														}
														for(int i=0;i<graph.E;i++) {
															int x=find(subsets,graph.edge[i].src);
															int y=find(subsets,graph.edge[i].dest);
															if(x==y)return 1;
															graph.Union(subsets, x, y);
														}
													
													return 0;
													
													
												}
												
											
											
										}
											
											
											
										
											
											
											
											
											
											
											
											
											
								
	}
	    