Background

Translated from Problem B of NERC 2018.

Problem Description

You are holding a dance party with some friends.

At this party, there are $n$ men and $m$ women. Originally, the dance is done in male-female pairs, but because there are not enough men, you cannot give every woman a male partner. So you invent a new dance form: one man pairs with two female partners.

Of course, when choosing partners, each woman gives a rating to each man. If the rating is $1$, it means the woman is willing to dance with that man. Only when both women are willing to dance with that man can they form a partner group.

As the organizer, you need to find the maximum number of such partner groups that can be formed, with the requirement that no person can appear in more than one group.

Input Format

The first line contains an integer $t (1 \leq t \leq 20)$, the number of test cases.

Then follow $t$ test cases. In each test case, the first line contains two integers $n$ and $m$. It is guaranteed that $1 \leq n,m$ and $n + m \leq 150$.

Then follows an $n \times m$ matrix, where $a_{i,j}$ indicates whether woman $j$ is willing to dance with man $i$.

Output Format

For each test case, output one line containing the maximum number of partner groups that can be formed.

2
2 3
111
111
3 4
0110
1100
0011

1
2

1
3 6
001100
111111
001100

2

Hint

The Constraints guarantee $1 \leq t \leq 20$, $1 \leq n, m$, and $n + m \leq 150$.

The figures below explain Sample 1 and Sample 2, where the bold parts show one feasible solution.

Sample 1:

Sample 2:

Translated by ChatGPT 5