Maximum Product of Three Numbers

You are given an array of integers. Your task is to find the maximum product of any three numbers chosen from this array. If the number of elements in the array is less than three, output NO SOLUTION.

Mathematically, if the sorted array is (a_0, a_1, \dots, a_{n-1}), then the answer is given by:

[ \max\Big( a_{n-1} \cdot a_{n-2} \cdot a_{n-3}, ; a_0 \cdot a_1 \cdot a_{n-1} \Big) ]

Solve the problem for multiple test cases.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T) representing the number of test cases. Each test case consists of two lines. The first line of a test case contains an integer (N) — the number of elements in the array. The second line contains (N) space-separated integers.

outputFormat

For each test case, output a single line on standard output (stdout) containing the maximum product of any three numbers from the array. If the array has fewer than three numbers, output NO SOLUTION.## sample

4
5
10 3 5 6 20
6
-10 -10 5 2 1 0
2
1 2
3
1 2 3

1200
500
NO SOLUTION
6