Maximum Product Subarray

You are given an array \(A\) of \(n\) integers (which may include zero and negative values). Your task is to find the maximum product of a contiguous subarray. In other words, if you select indices \(l\) and \(r\) with \(1 \leq l \leq r \leq n\), you want to maximize the product

[ P = \prod_{i=l}^{r} A_i ]

The subarray may consist of a single element. Note that the array can contain zero, which resets the product, and negative numbers, which may flip the sign. Consider these characteristics when computing the answer.

Input/Output: The input is read from stdin and the output should be written to stdout. For each test case, output the maximum product found in a new line.

inputFormat

The first line of input contains an integer \(T\) indicating the number of test cases. For each test case, the input is structured as follows:

• The first line contains an integer \(n\) representing the size of the array.
• The second line contains \(n\) integers separated by spaces, which represent the elements of the array \(A\).

outputFormat

For each test case, output a single line containing the maximum product of any contiguous subarray in the given array.

## sample

3
5
1 2 3 4 5
6
6 0 4 5 10 2
8
0 2 3 4 0 1 2 2

120
400
24

</p>