Bimatching

Time limit2sMemory limit512 MB

Summary

Given a grid of which cavaliers can dance with which ladies, find the maximum number of disjoint triples, each one cavalier with two compatible ladies.

Level: Medium7 of 10
Topics: Graph, BFS
Solved: No attempts yet

Statement

In the 19th century, dancing was one of the most important subjects that nobles learned at school. Balls were the main, and sometimes the only, chance to meet new people, both for romance and for business. However, many cavaliers died in wars, so a shortage of cavaliers at balls was common. To solve this, some dances were changed so that one cavalier asks two ladies for a dance instead of one. New dances were made for sets of triples, and ordinary dances stayed with sets of pairs.

Nowadays some communities rebuild historical dances, and there are still usually fewer cavaliers than ladies. So dances for lady-cavalier-lady triples are still studied.

Betty leads a popular community of historical dances. Some cavaliers and ladies dislike each other and do not want to dance together in the same triple. Betty knows all of these dislikes. She needs only a way to find the maximum number $t$ of triples that can be selected for a dance. She does not need to know the actual bimatching between cavaliers and ladies. She tells the dancers, "Now form $t$ triples, please. I know it is possible." Help Betty find the maximum lady-cavalier-lady bimatching capacity.

Input

The first line contains the number of test cases $t$ ( $1 \le t \le 20$ ). Each test case begins with a line containing the number $n$ of cavaliers and the number $m$ of ladies ( $1 \le n, m$ , $n + m \le 150$ ). The next $n$ lines each contain a string of $m$ characters, each 0 or 1. The character at position $\ell$ in row $c$ is 1 if and only if lady $\ell$ can be in one triple with cavalier $c$ . The sum of $n + m$ over all test cases does not exceed 150.

Output

For each test case, output the maximum number $t$ of triples that can be formed, on a single line.

Hint

In the illustration, each line means that a cavalier can dance with a lady. A bold line means that a cavalier asks a lady for a dance.

Examples2

Example 1
Input
```
2
2 3
111
111
3 4
0110
1100
0011
```
Expected output
```
1
2
```
Example 2
Input
```
1
3 6
001100
111111
001100
```
Expected output
```
2
```