Pokémon 保护协会在全球范围内保护着 Pokémon 及其栖息地。在最近的研究中，收集了关于 $h$ 个栖息地的数据。

每个栖息地可能居住着几种 Pokémon 物种。研究人员知道每个物种有多少条肢体。由于 Pokémon 动作敏捷且非常擅长隐藏，研究人员只能探测到每个栖息地中肢体的总数。

研究人员明白，可能无法确定每个物种的数量，但他们想了解还剩下多少不确定性。有多少种不同的 Pokémon 组合会产生观测到的肢体总数？

输入格式

第一行包含一个整数 $h$ ($1 \le h \le 1024$)，表示栖息地的数量。接下来的 $h$ 行包含每个栖息地的描述。

每行以两个整数 $t$ 和 $s$ ($0 \le t \le 10^9, 1 \le s \le 3$) 开头，其中 $t$ 是肢体总数，$s$ 是栖息地中的物种数量。随后是 $s$ 个整数 $l_i$ ($1 \le l_i \le 16$)，表示每个物种的肢体数量。

输出格式

输出每个栖息地中可能的 Pokémon 组合数量。输出应包含 $h$ 行，每行一个整数。

样例

输入格式 1

3
6 1 3
6 2 2 3
6 3 1 2 3

输出格式 1

1
2
7

输入格式 2

4
1000000000 3 1 1 1
0 3 2 4 5
17 2 2 4
34 3 5 3 2

输出格式 2

500000001500000001
1
0
25

说明

为了方便举例，我们使用 LaTeX Pokémon：$\text{O}$ 有一条肢体，$\angle$ 有两条肢体，$\exists$ 有三条肢体。

在第一个样例中，所有三个栖息地都有 6 条肢体。

在第一个样例中，第一个栖息地只有一个 Pokémon 物种 —— $\exists$。所以它很可能是一个包含 $\exists\exists$ 的年轻家庭。

在第二个栖息地中，有两种 Pokémon 物种：$\angle$ 和 $\exists$。所以它要么是 $\angle\angle\angle$，要么是 $\exists\exists$。

第三个栖息地可能包含三种 Pokémon 物种中的任意一种：$\text{O}$、$\angle$ 和 $\exists$。共有七种可能的组合：$\exists\exists, \angle\angle\angle, \text{O}\angle\exists, \text{O}\text{O}\angle\angle, \text{O}\text{O}\text{O}\exists, \text{O}\text{O}\text{O}\text{O}\angle, \text{O}\text{O}\text{O}\text{O}\text{O}\text{O}$。

在第二个样例中，第一个栖息地有三种 Pokémon 物种，但它们都只有一条肢体：$\partial, \text{O}$ 和 $\rho$。共有 $10^9$ 条肢体，组合数为 $\sum_{i=0}^{10^9} (i + 1)$。

在第二个栖息地中，没有探测到肢体。所以很遗憾，该地区没有剩下的 Pokémon。

在第三个栖息地中，所有 Pokémon 的肢体数量都是偶数，因此不可能有 17 条肢体。