이중 매칭

19세기 학교에서 귀족이 배우는 가장 중요한 과목 중 하나가 춤이었다. 무도회는 새로운 사람을 만나는 주된 기회였고, 때로는 유일한 기회이기도 했다. 연애와 사업 모두에 쓰였다. 그런데 많은 기사가 전쟁에서 목숨을 잃어서 무도회에 기사가 모자라는 일이 흔했다. 이를 해결하려고 기사 한 명이 한 명이 아니라 두 명의 숙녀에게 춤을 청하도록 바꾼 춤이 생겼다. 새로운 춤은 세 명이 한 조를 이루는 삼중조를 위해 만들어졌고, 기존 춤은 두 명이 한 조를 이루는 짝을 대상으로 그대로 남았다.

지금도 역사 춤을 복원하는 커뮤니티가 있으며, 기사 수는 보통 숙녀 수보다 적다. 그래서 숙녀-기사-숙녀 삼중조 춤도 여전히 연구된다.

Betty는 인기 있는 역사 춤 커뮤니티의 리더이다. 일부 기사와 숙녀는 서로를 싫어해서 같은 삼중조에서 함께 춤추기를 원하지 않는다. Betty는 커뮤니티의 이런 반감을 모두 알고 있다. 그녀에게 필요한 것은 춤에서 선택할 수 있는 삼중조의 최대 개수 $t$를 찾는 방법뿐이다. 기사와 숙녀 사이의 실제 짝짓기를 알 필요는 없다. 그녀는 춤을 추는 사람들에게 "이제 $t$개의 삼중조를 만들어 주세요. 가능하다는 걸 알고 있어요"라고 말하곤 한다. Betty를 도와 숙녀-기사-숙녀 이중 매칭의 최대 용량을 구하라.

첫 줄에 테스트 케이스의 개수 $t$가 주어진다 ($1 \le t \le 20$). 각 테스트 케이스의 첫 줄에는 기사의 수 $n$과 숙녀의 수 $m$이 주어진다 ($1 \le n, m$, $n + m \le 150$). 이어서 $n$개의 줄에 각각 0과 1로 이루어진 길이 $m$의 문자열이 주어진다. $c$번째 줄의 $\ell$번째 문자가 1이면 기사 $c$와 숙녀 $\ell$이 한 삼중조에 함께 들어갈 수 있다. 모든 테스트 케이스의 $n + m$ 합은 150을 넘지 않는다.

각 테스트 케이스마다 만들 수 있는 삼중조의 최대 개수 $t$를 한 줄에 출력한다.

그림에서 각 선은 기사가 숙녀와 춤출 수 있음을 뜻한다. 굵은 선은 기사가 숙녀에게 춤을 청하는 경우를 뜻한다.