Solve the programming task below in a Python markdown code block.
Chef is playing an easier variation of the board game ‘Risk’ with his friend Mike. There is an $N * M$ grid, depicting the world map. Each cell of the grid is either $1$ or $0$ where $1$ denotes that there is land on this cell, while $0$ denotes water. 

In a turn, a player can capture an uncaptured cell that has land, and keep capturing neighbouring cells that share a side with it if they are on land. A cell once captured by a player can't be captured again by another player. The game continues till no uncaptured cell has land. Each player wants to be in control of as many cells of land as possible in total when the game finishes. Find the maximum number of cells of land that Chef can capture if he plays second, and both players play optimally. 

------ Input: ------

First line will contain $T$, number of testcases. Then the testcases follow.
Each testcase contains $N + 1$ lines of input.
First line will contain $2$ space separated integers $N$ and $M$ denoting the size of the grid. 
Each of the next $N$ lines contains a binary string of length $M$ depicting the map. 

------ Output: ------
For each testcase, output in a single line answer to the problem.

------ Constraints  ------
$1 ≤ N, M ≤ 10^{5}$
Each character in the grid is either $0$ or $1$
There's atleast $1$ land on the grid
Sum of $N * M$ over all testcases is almost $10^{6}$.

----- Sample Input 1 ------ 
3

4 4

1001

0110

0110

1001

2 2

11

11

3 3

100

010

001
----- Sample Output 1 ------ 
2

0

1
----- explanation 1 ------ 
In test case 1, if both players play optimally, it takes $5$ steps to finish the game:

Step 1: First Mike chooses the cells $\{(2, 2), (2, 3), (3, 2), (3, 3)\}$ adding $4$ to his score.

Step 2: Second Chef chooses the cell $\{(1, 1)\}$ adding $1$ to his score.

Step 3: Next Mike chooses the cell $\{(1, 4)\}$ adding $1$ to his score.

Step 4: Next Chef chooses the cell $\{(4, 1)\}$ adding $1$ to his score.

Step 5: Finally, Mike chooses the cell $\{(4, 4)\}$ adding $1$ to his score.

Hence total score of Chef is $1 + 1 = 2$.