题目描述

Karina 有一个 $n$ 个整数的数组 $a_1,a_2,a_3,\cdots,a_n$。她还喜欢将数字乘在一起，所以她认为一对数字的美在于它们的乘积。数组的美就是数组中相邻的一对元素的最大美。

例如，对于 $n = 4$，$a =[3,5,7,4]$，数组的美妙之处是 $max(3\times5,5 \times 7,7 \times 4) = max (15, 35, 28) = 35$。

Karina 希望她的阵列尽可能的漂亮。为了实现她的目标，她可以从数组中删除一些元素（可能为零）。在 Karina 删除她想要的所有元素后，数组必须包含至少两个元素。

不幸的是，Karina 没有足够的时间来完成她的所有任务，所以她要求你计算她通过删除任意数量的元素（可能为零）所能获得的数组的最大美感。

输入格式

本题有多组数据。

第一行一个整数 $t(1 \leq t \leq 10^4)$，表示数据组数。

对于每组数据：

第一行为一个整数 $n(2 \times 10^5)$，表示数组 $a$ 的长度。

第一行包含 $n$ 个整数 $a_1,a_2,a_3,\cdots,a_n(-10^9 \leq a_i \leq 10^9)$，代表数组 $a$ 的元素。

所有测试数据中所有 $n$ 值的总和不超过 $2 \times 10^5$。

输出格式

对于每组测试数据：

输出 Karina 可以得到数组的最大美感。

感谢

样例

7
4
5 0 2 1
3
-1 1 0
5
2 0 -1 -4 0
6
-8 4 3 7 1 -9
6
0 3 -2 5 -4 -4
2
1000000000 910000000
7
-1 -7 -2 -5 -4 -6 -3

10
0
4
72
16
910000000000000000
42