To increase the probability of the contact with aliens, humans tried to draw some pictures on metals and place them on the planets which humans can reach. Once aliens reach the planets and find the pictures, they’ll, probably, know what the pictures mean and raise the interests to find earth and contact with humans. But the problem is what kind of pictures should be chosen for. After some discussion, human beings had two common conclusions. One is that it must be hieroglyphic and the other is that it must show up our civilization. To satisfy the conditions, humans paid a lot of efforts. Finally, they found some problems related to computer science are appropriate. The followed picture is one candidate.
The secret behind the picture is that it’s an optimal problem to paint the fewest empty cells to black ones to let all rows and columns in the resulted grid have more than 2 black cells or none. However, it’s really difficult to let aliens know the secret if only one pair of grids is given. To overcome that, you should help humans to generate a series of grids like that.
Before all test cases, there will be a positive number in a line indicates the number of followed test cases. The first line of each test case contains two positive integers, n and m, where both n and m are greater than 2 and less than 100. The remaining lines of each test case are n by m grid, where 0 represents an empty cell and 1 represents a black one. Note, no spaces existed between any two consecutive cells.
Since there will be multiple solutions for a fixed puzzle, output the minimum number of painted empty cells in a line without any leading or trailing spaces.
2 3 3 000 010 000 5 8 00000000 01000100 00000000 00000000 01000000
8 6
Migrated from old NTUJ.
| No. | Testdata Range | Score |
|---|