Largest Product of Three

Given an array of integers, your task is to find the largest product that can be made by multiplying any three integers in the array.

The answer is determined by considering two cases:

• The product of the three largest numbers.
• The product of the two smallest (most negative) numbers and the largest number.

This can be expressed using the formula: \[ \max\{a_{n-3} \times a_{n-2} \times a_{n-1},\; a_{0} \times a_{1} \times a_{n-1}\} \]

It is guaranteed that each test case has at least three numbers.

inputFormat

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

• The first line contains an integer N (N ≥ 3), 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 largest product of any three integers from the given array.

## sample

1
5
1 2 3 4 5

60

</p>