A crossword puzzle consists of an MxN grid with M rows and N columns. Initially, some of the squares are filled, and some of the squares are empty, which are to be filled by answering the questions. The answers to the questions are written in the empty squares until we reach the puzzle boundaries or initially filled squares.
Filled squares can contain answers for at most two questions, one horizontally, and one vertically. An initially filled square contains a horizontal question if a square to the right exists and is empty. Similarly, an initially filled square contains a vertical question if a square beneath it exists and is empty.
Since you are an expert crossword puzzle solver, you already know all the answers. Now you want to know what could be the minimum number of questions that you needed to answer to solve a given puzzle.
Input
The first line in the input will start with an integer T, (1 <= T <= 30) the number of test cases.
The first line for each test contains two integers, M and N, (2 <= M <= 512, 2 <= N, <= 12) where M and N are the numbers of rows and columns respectively. Each of the next M lines contains N characters, either ‘0’ or ‘1’, denoting an initially empty and an initially filled square respectively. It is guaranteed that all squares from the first row and first column will be filled with ‘1’ and there will be at least one square filled with ‘0’.
Output
For each test case, just output one line containing the minimum number of questions that needed to be answered.
Sample
| Input | Output |
|---|---|
3 4 5 11111 10000 10000 10000 6 4 1111 1011 1000 1011 1010 1000 9 8 11111111 10000000 10001000 10010001 11100001 10100110 10001000 10100001 10010001 | 3 4 14 |
