1003. 大户爱的宿舍

题目描述

大户爱是一个宿舍管理员，新生入学需要大户爱来分配宿舍。每间宿舍都有 K 个床位，编号从 1 到 K。一共有 N 个新生，新生不一定能接受所有床位，所以每个新生会给出自己能接受的床位编号。大户爱希望尽可能多地启用宿舍。每间启用的宿舍都必须恰好住满 K名新生，并且每名新生都必须被分配到自己能够接受的床位。请你求出最多能够启用多少间宿舍。

输入格式

第一行输入一个整数 T，表示数据组数。对于每组数据：第一行输入两个整数 N, K。接下来 N 行每行输入一个长度为 K 的 01 串，01 串的下标从 1 开始，第 i 位为 1 表示该新生接受床位 i，第 i 位为 0 表示该新生不接受床位 i。

1 ≤ T ≤ 25, 1 ≤ N ≤ 1000, 1 ≤ K ≤ 30。保证所有 01 串中 1 的数量之和 ≤ 1.5 × 105。

输出格式

输出最大可能启用的宿舍数。

样例输入

1
5 4
1000
0100
0010
0001
1111

样例输出

1

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第10场）