Highest Product of Three

Given an array of integers, determine the maximum product that can be achieved by multiplying any three numbers from the array. In mathematical terms, let the array be \( A = [a_1, a_2, \dots, a_n] \). The answer is given by:

\[ \max\{a_1 \cdot a_2 \cdot a_n,\; a_{n-2} \cdot a_{n-1} \cdot a_n\}\]

Note that the array may contain negative numbers. Therefore, the product of the two smallest numbers (which might be negative) with the largest number can sometimes be the maximum.

inputFormat

The input is read from standard input (stdin). The first line contains an integer ( T ) representing the number of test cases. For each test case, the first line contains an integer ( N ) denoting the number of elements in the array. The second line contains ( N ) space-separated integers.

outputFormat

For each test case, print the maximum product of any three integers from the array. Each answer should be printed on a new line to standard output (stdout).## sample

1
5
1 2 3 4 5

60