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.

// https://codeforces.com/contest/1406/problem/B
import java.util.*;
import java.io.*;

public class B670 {
	/*
	 * Yu Lim's OP Template
	 */
	// You got this lmao >:)
	static class Fscan {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		// pass (new FileInputStream("'FILE NAME'.in")) for reading files
		// pass (System.in) for reading standard input
		public Fscan(InputStream stream) {
			this.stream = stream;
		}

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

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

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

		String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}

		// returns the next N lines in an integer array
		// each line contains 1 integer
		// delta is how much to add to each input (can be negative)
		// delta is useful if you want to convert 1-based input to 0-based
		int[] nextInts(int N, int delta) {
			int[] ret = new int[N];
			for (int i = 0; i < N; i++)
				ret[i] = nextInt() + delta;
			return ret;
		}

		// returns the next N lines in a long array
		// each line contains 1 long
		// delta is how much to add to each input (can be negative)
		// delta is useful if you want to convert 1-based input to 0-based
		long[] nextLongs(int N, long delta) {
			long[] ret = new long[N];
			for (int i = 0; i < N; i++)
				ret[i] = nextLong() + delta;
			return ret;
		}

		// returns the next N lines in a double array
		// each line contains 1 double
		double[] nextDouble(int N) {
			double[] ret = new double[N];
			for (int i = 0; i < N; i++)
				ret[i] = nextDouble();
			return ret;
		}

		// returns the next N lines in a string array
		// each line contains 1 string
		String[] next(int N) {
			String[] ret = new String[N];
			for (int i = 0; i < N; i++)
				ret[i] = next();
			return ret;
		}

		// returns the next N lines in a string array
		// each line contains 1 string/sentence
		String[] nextLines(int N) {
			String[] ret = new String[N];
			for (int i = 0; i < N; i++)
				ret[i] = nextLine();
			return ret;
		}

		// close the stream (IMPORTANT)
		void close() throws IOException {
			stream.close();
		}
	}/*
		 * ^ ^ / \ //\ |\___/| / \// .\ /O O \__ / // | \ \ / / \/_/ // | \ \
		 * 
		 * @___@' \/_ // | \ \ | \/_ // | \ \ | \/// | \ \ _|_ / ) // | \ _\ '/,_ _ _/ (
		 * ; -. | _ _\.-~ .-~~~^-. ,-{ _ `-.|.-~-. .~ `. '/\ / ~-. _ .-~ .-~^-. \ `. { }
		 * / \ \ .----~-.\ \-' .~ \ `. \^-. ///.----..> c \ _ -~ `. ^-` ^-_ ///-._ _ _ _
		 * _ _ _}^ - - - - ~ ~--, .-~ /.-'
		 */

	// Main/Driver method
	public static void main(String[] args) throws IOException {
		// Fast Scanner and PrintWriter for Standard Input/Output
		Fscan sc = new Fscan(System.in);
		PrintWriter pw = new PrintWriter(System.out);

		int T = sc.nextInt();
		for (; T > 0; T--) {
			int N = sc.nextInt();
			long[] arr = new long[N];
			long[][] dpmin = new long[N][6];
			long[][] dpmax = new long[N][6];
			for(int i = 0; i < N; i++) {
				Arrays.fill(dpmin[i], Long.MAX_VALUE);
				Arrays.fill(dpmax[i], Long.MIN_VALUE);
			}
			for (int i = 0; i < N; i++) {
				arr[i] = sc.nextInt();
			}
			Arrays.sort(arr);
			for(int i = 0; i < N; i++) {
				dpmin[i][1] = arr[i];
				dpmax[i][1] = arr[i];
			}
			
			long[] min = new long[6];
			Arrays.fill(min, Long.MAX_VALUE);
			long[] max = new long[6];
			Arrays.fill(max, Long.MIN_VALUE);
			min[1] = max[1] = arr[0];
			for (int i = 0; i < N; i++) {
				for (int j = 2; j <= 5; j++) {
					if (j - 1 > i)
						break;
					if (arr[i] < 0) { // arr[i] is negative
						dpmax[i][j] = arr[i] * min[j - 1];
						dpmin[i][j] = arr[i] * max[j - 1];
					} else { // arr[i] is positive
						dpmax[i][j] = arr[i] * max[j-1];
						dpmin[i][j] = arr[i] * min[j-1];
					}
				}
				for (int j = 1; j <= 5; j++) {
					if(j - 1 > i)
						break;
					if (dpmin[i][j] < min[j])
						min[j] = dpmin[i][j];
					if (dpmax[i][j] > max[j])
						max[j] = dpmax[i][j];
				}
			}
			
			long ans = Long.MIN_VALUE;
			for(int i = 0; i < N; i++)
				if(dpmax[i][5] > ans)
					ans = dpmax[i][5];
			pw.println(ans);
		}

		sc.close();
		pw.close();
	}
}
