Description

有n个整数从左往右排成一行，构成一个序列a。如果通过删除原序列的若干个数（可以是删除0个），其他数保持位置不动，那么

得到的序列就称为“子序列”。记sum表示序列a的所有数的总和，即sum=a[1]+a[2]+a[3]+...+a[n]。

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

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

Input Format

多组测试数据。

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

每组测试数据格式如下：

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

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

Output Format

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

Source