Largest Product of Three Numbers

You are given several test cases. In each test case, you are provided with an integer n followed by n integers. Your task is to select three distinct numbers from the list such that their product is maximized. If the list contains less than three numbers, output 0.

Note that the maximum product can be obtained either by multiplying the three largest numbers or by multiplying the two smallest (possibly negative) numbers with the largest number.

The answer for each test case should be output on a new line.

The mathematical formula for the answer can be expressed in LaTeX as follows:

$$\max( a_{n-2} \times a_{n-1} \times a_n,\, a_1 \times a_2 \times a_n)$$

inputFormat

The first line contains an integer T indicating the number of test cases. For each test case:

• The first line contains an integer n representing the number of integers.
• The second line contains n integers separated by spaces.

If n < 3, print 0 for that test case.

outputFormat

For each test case, output a single line containing the maximum product that can be achieved by multiplying three distinct numbers from the list.

## sample

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

60
21
120

</p>