Largest Product Subarray

You are given an integer array and your task is to find the contiguous subarray within the array that has the largest product. This problem can be formally stated as follows:

Given an array \(a = [a_1, a_2, \ldots, a_n]\), find the maximum value of the product \(a_i \times a_{i+1} \times \cdots \times a_j\) for any \(1 \leq i \leq j \leq n\). Note that the array may contain negative numbers and zeros.

Example: For the array [2, 3, -2, 4], the contiguous subarray [2, 3] has the largest product of 6.

inputFormat

The input begins with an integer T indicating the number of test cases. Each test case is described in two lines:

• The first line contains an integer n representing the number of elements in the array.
• The second line contains n space-separated integers representing the elements of the array.

outputFormat

For each test case, print a single integer on a new line – the maximum product of any contiguous subarray.

## sample

1
4
2 3 -2 4

6

</p>