Minimum Modifications for Alternating Grid Path

You are given a grid with n rows and m columns, where each cell contains either 0 or 1. A path from the top‐left cell to the bottom‐right cell is allowed only if you move either right or down at each step. A path is considered alternating if every two consecutive cells in the path have different values (i.e. if one cell is 0, the next must be 1, and vice versa).

You are allowed to change the value of any cell at a cost of 1 per change. Your task is to compute the minimum number of modifications required so that there exists at least one alternating path from the top‐left to the bottom‐right cell.

In other words, if we define a cost function for each cell modification as \[ \text{cost} = \begin{cases} 0, & \text{if the cell already has the desired value} \ 1, & \text{otherwise} \end{cases} \] find the minimum total cost needed to modify the grid such that there exists a valid alternating path.

inputFormat

The input is read from standard input (stdin) and has the following format:

T
n1 m1
row1
row2
... (n1 rows for test case 1)
n2 m2
row1
row2
... (n2 rows for test case 2)
... 

Here, T denotes the total number of test cases. For each test case, the first line contains two space-separated integers representing the number of rows (n) and columns (m). This is followed by n lines, each containing m space-separated integers (0 or 1) which represent the grid.

outputFormat

For each test case, output a single integer on a new line representing the minimum number of changes required to create an alternating path from the top-left to the bottom-right corner.

## sample

1
2 2
1 0
0 1

0

</p>