Maximum Product of Three Numbers

Given an array of integers, your task is to determine the maximum product of any three distinct numbers in the array.

If the number of elements in the array is less than three, output \(-1\).

Note that even if the array contains negative numbers, the product of two negatives can become positive. In mathematical notation, for an array \(A\) with \(|A| \ge 3\), the answer is given by:

\[ \max\Big\{A_{i} \times A_{j} \times A_{k} \;:\; i, j, k \text{ are distinct}\Big\} \]

Otherwise, if \(|A| < 3\), output \(-1\).

inputFormat

The first line contains an integer \(T\) representing the number of test cases. Each test case consists of two lines. The first line of each test case 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, output a single line containing the maximum product of any three distinct numbers. If the array has fewer than three numbers, output \(-1\).

## sample

5
5
1 10 3 7 6
4
-10 -10 5 2
2
1 2
4
-5 -6 -4 -7
4
1 2 3 3

420
500
-1
-120
18

</p>