Maximum Product Subarray

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product. In other words, for a subarray defined from index l to r, you need to maximize

$$P = \prod_{i=l}^{r} nums_i$$

The array may contain positive, negative values, or zero. You are required to process multiple test cases. For each test case, the first integer indicates the number of elements in the array, followed by the array elements.

Good luck!

inputFormat

The input begins with an integer t representing the number of test cases. For each test case, the first line contains an integer n indicating the number of elements, followed by a line with n space-separated integers representing the array.

Example:

2
4
2 3 -2 4
5
-2 0 -1 0 2

outputFormat

For each test case, output the maximum product obtainable from any contiguous subarray. Each result should be printed on a new line.

## sample

2
4
2 3 -2 4
5
-2 0 -1 0 2

6
2

</p>