题目描述

有 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