Inco Gnito 先生试图潜入 Entership Starprise，并被指派协助总工程师 Forgie 进行维修工作。Forgie 随身携带了一些工具，并会反复要求 Inco 提供这些工具的某个子集。只有当 Inco 将完全正确的工具放在 Forgie 面前时，他才会拿走这些工具，使用它们，然后将它们归还给 Inco。这个过程会一直重复，直到维修工作完成。这听起来很简单，但问题在于 Inco 根本不知道这些工具叫什么名字！幸运的是，Inco 学习能力很强，因此他能够利用之前所有错误和成功的经验来尝试寻找新的工具子集。另一方面，如果他非常不幸，他可能会被困在 Forgie 那里很长很长时间，甚至可能被发现是间谍。

计算 Inco 总共必须向 Forgie 提供多少个不同的工具子集，假设他在这次任务中运气最差。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。每个测试用例的第一行包含两个整数 $N$（工具的数量）和 $K$（Forgie 将要求的不同子集的数量）。下一行包含 $N$ 个以空格分隔的工具名称，由最多 25 个小写字母 'a'-'z' 和 '-' 组成。接下来有 $K$ 行，每行包含一个整数 $M$，随后是 $M$ 个上述工具的名称。在同一个测试用例中，工具名称是唯一的，且不同测试用例之间的工具互不相关。

输出格式

对于每个测试用例，输出 Inco 在假设他能从任务中吸取所有经验的情况下，可能必须向 Forgie 提供的最大子集数量。答案可能非常大，因此请输出结果对 $2^{31} - 1$ 取模后的值。

数据范围

• $0 < T \le 100$
• $0 < N \le 1000$
• $0 < K \le 100$
• $0 < M \le N$

样例

样例输入 1

2
3 3
tricorder quantum-flux-regulator hyperspanner
1 tricorder
1 quantum-flux-regulator
1 hyperspanner
5 4
pulse-drill phase-coil-resonator duct-tape crowbar optronic-coupler
2 phase-coil-resonator optronic-coupler
2 pulse-drill optronic-coupler
1 crowbar
1 duct-tape

样例输出 1

6
19