You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

连通块

题目描述

给定 $m$ 个不同的整数 $a_1, a_2, \cdots, a_m$，每个数都属于 $[0,2^n−1]$ 的范围内.

一个图按照如下约束建立：

如果整数 $X$ 和 $Y$ 满足 $X\&Y=0$（$\&$ 是按位与运算），则 $X$ 和 $Y$ 由一条无向边连接.

请计算图中连通分量的数量.

输入格式

输入包含 $T$ 组测试数据.

第一行包含一个整数 $T$.

每组数据第一行包含两个整数 $n,m$.

第二行包含 $m$ 个整数 $a_1, a_2, \cdots, a_m$.

输出格式

每组数据输出一行结果，表示连通分量的个数。

数据范围

• $1\leq T \leq 10$
• $0\leq n \leq 22$
• $1\leq m\leq 2^n$
• $0\leq a_i < 2^n$

输入输出样例

输入样例：

3
2 3
1 2 3
5 5
5 19 10 20 12
5 6
5 19 10 20 12 0

输出样例：

2
2
1