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.
// Java program to find maximum possible product of 
// sub-sequence of size k from given array of n 
// integers 
import java.io.*; 
import java.util.*; 

public class GFG {  
	static long maxProductSubarrayOfSizeK(long A[], int n, int k) 
	{ 
		Arrays.sort(A); 

		long product = 1; 

		if (A[n - 1] == 0 && k % 2 != 0) 
			return 0; 

		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; 

		if (k % 2 != 0) { 
			product *= A[j]; 
			j--; 
			k--; 
		} 

		k >>= 1; 

		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; 
	} 

	// driver program 
	public static void main(String[] args) 
	{ 
	     Scanner sc=new Scanner(System.in);
	   // BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	    int t=1;
	    t=sc.nextInt();
	   // int t=Integer.parseInt(br.readLine());
	    while(--t>=0){
	        int n=sc.nextInt();
	         //     int n=Integer.parseInt(br.readLine());
	          //     int k=sc.nextInt();
	          //    String s=br.readLine();
	         //     StringTokenizer st=new StringTokenizer(br.readLine());
	         //      int n=Integer.parseInt(st.nextToken());
	         long a[]=new long[n];
	        for(int i=0;i<n;i++)a[i]=sc.nextLong();
	       System.out.println(maxProductSubarrayOfSizeK(a, n, 5));
	       
	       
	       
	      //  for(int i=0;i<n;i++)
	      //  System.out.print(arr[i]+" ");
	        
	     
	        
	    }
	} 
} 

// Contributed by Pramod Kumar 
