题目描述

有 n 个整数从左往右排成一行，构成一个序列 a 。如果通过删除原序列的若干个数（可以是删除 0 个），其他数保持位置不动，那么得到的序列就称为 “子序列” 。记 sum 表示序列 a 的所有数的总和，即 sum=a[1]+a[2]+a[3]+...+a[n] 。

如果一个 “子序列” 的各个数加起来的和等于 sum-1 ，那么这个 “子序列” 就是 “优美子序列” 。

问：有多少个不同的 “优美子序列”？

输入格式

多组测试数据。

第一行，一个整数 G ，表示有 G 组测试数据， 1 <= G <= 10000 。

每组测试数据格式如下：

第一行，一个整数 n , 1 <= n <= 60 。

第二行， n 个整数，第 i 个整数是 a[i] 。0 <= a[i] <= ${10}^9$ 。

输出格式

共 G 行，每行一个整数。

样例

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
0
2
4
4