C. Shiori Novella's 3D Showcase
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an $$$n \times m$$$ grid of $$$0$$$s and $$$1$$$s, flip the minimum number of bits such that no $$$0$$$ is vertically or horizontally adjacent to another $$$0$$$, and no $$$1$$$ is vertically or horizontally adjacent to another $$$1$$$.

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ $$$-$$$ the number of test cases.

The first line of each test case contains a two integers $$$n$$$ and $$$m$$$ $$$(1 \le n \le 1000, 1 \le m \le 1000)$$$ $$$-$$$ the number of rows and columns of the grid.

Each of the following $$$n$$$ lines contains $$$m$$$ characters describing the cells of the grid. Each character is either $$$0$$$ or $$$1$$$.

It is guaranteed the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, print a single integer $$$-$$$ the number of bit flips such that no $$$0$$$ is next to another $$$0$$$ and no $$$1$$$ is next to another $$$1$$$.

Example
Input
2
3 4
0001
1010
0101
2 1
0
1
Output
1
0