该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

徐老师有一个整数数组，他想找出一个连续子数组，使得该子数组中所有元素的乘积尽可能大。请输出这个最大乘积。

注意：数组中的元素可能是负数或$0$。例如，数组$[2, 3, -2, 4]$的最大积子数组是$[2, 3]$，乘积为$6$。

Format

Input

第一行一个正整数$T(1 \leq T \leq 10)$，表示测试组数。

对于每组测试，第一行一个正整数$n(1 \leq n \leq 10^5)$。

第二行$n$个整数$a_i(|a_i| \leq 10^4)$，表示数组元素。

Output

对于每组数据，输出一行一个整数，表示最大连续子数组乘积。

Samples

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

6
0

Limitation

1s, 1024KiB for each test case.