Migrated from Lutece 658 Krolia的礼包难题

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Krolia新开了一家礼品店，每天都要接到很多礼品的订购。Krolia送出去的礼品都需要包装。Krolia最后给顾客的是一个或者多个礼包，礼包里面装的礼物刚好是顾客订购的那些礼物。礼包由一些礼品组成，礼包里面每种礼品至多只能有一件。每一种礼包都需要包装纸。内容相同的礼包需要相同的包装纸，内容不同的礼包则需要不同的包装纸。Krolia希望包装纸的种类最少，因为设计一种包装纸很费事。并且Krolia要求一种礼品只能在一种礼包中出现，否则最后配送礼品的时候选择如何打包会很麻烦。现在Krolia的礼品店总共有$n$种礼品，已知明天客人的订购详细，问Krolia最少需要多少种包装纸。

Input

有多组测试数据。输入的第一行是整数$T$($0 < T\leq100$)，表示测试数据的组数。每一组测试数据的第一行有两个整数，分别为整数$n,m$($1\leq n,m\leq 50$)，表示有$n$种礼品，$m$个订购。接下来$m$行，每行$n$个数，第$i$个数为$1$表示该顾客的订单中购买了第$i$种礼品，为$0$则表示没有购买。

Output

每组测试数据一个整数，表示需要的最少包装纸种类数。

Samples

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

2
3

Note

样例$1$：把礼品123打包成礼包1，需要一种包装纸。把礼品45打包成礼包2，需要一种包装纸。

样例$2$：把礼品1打包成礼包1，需要一种包装纸。把礼品2打包成礼包2，需要一种包装纸。把礼品3打包成礼包3，需要一种包装纸。最后给顾客1礼包12，给顾客2礼包13。

Resources

KroliaFansClub