题目描述

有 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