题目描述

Slavic 正在为朋友准备生日礼物。他有一个长度为 $n$ 的数字数组 $a$，礼物将是这些数字的乘积。因为 Slavic 是个想要做出最大乘积的好孩子，他想要将其中一个数字加 $1$。

Slavic 能得到的最大乘积是多少？

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 9$），表示数字的个数。

每个测试用例的第二行包含 $n$ 个用空格分隔的整数 $a_i$（$0 \leq a_i \leq 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

样例说明

由 ChatGPT 4.1 翻译

来源

Codeforces 1873B，英文题名 Good Kid。