该公司生产了一种非常受欢迎的自动控制机（Automatic Control Machine，简称 ACM）。由于其功能全面且强大，公司准备在销售多年后对其进行重新设计。新版本的 ACM 在上市前仍需经过一系列测试以确定其可靠性。由于功能繁多，每个测试数据集只能检测其中的一部分。当然，产品必须在所有功能都经过测试后才能上市。由于每次测试都有时间和材料成本，他们希望尽可能减少测试次数。假设运行每个测试数据集的成本相同，你的任务是找到能够覆盖所有功能测试的最小测试数据集数量。例如，如果有 5 个功能需要测试，且有 6 个测试数据集，每个数据集覆盖的功能如下：

• 测试数据集 $a$: 1
• 测试数据集 $b$: 2, 5
• 测试数据集 $c$: 2, 3, 4
• 测试数据集 $d$: 1, 3, 5
• 测试数据集 $e$: 1, 3, 4
• 测试数据集 $f$: 3, 5

虽然 $\{a, b, c\}$ 可以完成任务，但 $\{c, d\}$ 在节省时间和金钱方面表现更好。

输入格式

输入文件的第一行包含一个正整数 $T$，表示机器的数量。对于每台机器，第一行包含两个整数 $n$ 和 $m$，分别表示需要测试的功能数量和测试数据集的数量。接下来有 $m$ 行，每行是一个长度为 $n$ 的二进制字符串，表示该测试数据集是否能检测到相应的功能（1 表示能，0 表示不能）。

输出格式

输出 $T$ 行。每行应为测试该机器所有功能所需的最小测试数据集数量。如果无法测试该机器的所有功能，则输出 -1。

数据范围

• 机器数量 $0 < T \le 10$
• 待测试功能数量 $0 < n \le 500$
• 测试数据集数量 $0 < m \le 15$

样例

样例输入 1

5
3 3
100
011
111
5 6
10000
01001
01110
00111
10110
00101
6 7
000010
011000
100100
001000
000010
010000
110001
7 6
1001001
1001000
0001101
0010110
0110011
0100001
2 1
01

样例输出 1

1
2
4
3
-1