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

Slavic 正在为朋友的生日准备礼物。他有一个由 $n$ 个数字组成的数组 $a$，礼物的价值定义为这些数字的乘积。

因为 Slavic 是个想让乘积尽可能大的乖孩子，他想恰好选择一个数字，并将其加 $1$。

请你计算：他能得到的最大乘积是多少？

输入格式

第一行输入一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数量。

每个测试用例包含两行：

• 第一行一个整数 $n$（$1 \le n \le 9$），表示数组中数字个数。
• 第二行包含 $n$ 个用空格分隔的整数 $a_i$（$0 \le a_i \le 9$），表示数组中的数字。

输出格式

对每个测试用例输出一行一个整数：将恰好一个数字加 $1$ 后可得到的最大乘积。

样例

输入：

4
4
2 2 1 2
3
0 1 2
5
4 3 2 3 4
9
9 9 9 9 9 9 9 9 9

输出：

16
2
432
430467210