Luntik 早上出来散步,发现了一个长度为 $$$n$$$ 的数组 $$$a$$$。他计算了数组元素的总和 $$$s$$$ ($$$s= \sum_{i=1}^{n} a_i$$$)。如果数组 $$$a$$$ 中的数字之和等于 $$$s-1$$$,则 Luntik 称该子序列几乎已满。
Luntik 确实想知道数组 $$$a$$$ 的几乎完整子序列的数量。但他需要回家,所以他请你解决这个问题!
如果 $$$x$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$y$$$ 获得,则序列 $$$x$$$ 是序列 $$$y$$$ 的子序列。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。接下来的 $$$2 \cdot t$$$ 行包含测试用例的描述。每个测试用例的描述由两行组成。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 60$$$) — 数组的长度。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。
输出
对于每个测试用例,打印数组中几乎完整的子序列的数量。
示例
输入 #1
5 5 1 2 3 4 5 2 1000 1000 2 1 0 5 3 0 2 1 1 5 2 1 0 3 0
输出 #1
1 0 2 4 4
注意
在第一个测试用例中,$$$s=1+2+3+4+5=15$$$,所有子序列中只有$$$(2,3,4,5)$$$是近满子序列,其中的总和等于$$$2+3+4+5=14=15-1$$$。
在第二个测试用例中,没有几乎完整的子序列。
在第三个测试用例中,$$$s=1+0=1$$$,几乎满的子序列是$$$(0)$$$ 和$$$()$$$(空子序列的总和是$$$0$$$)。