C. Flipping Rectangles
time limit per test
7 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Santi is a great lover of horseback riding and loves to spend time on his horse Lucy. However, lately he cannot ride comfortably because he knows that he has not yet managed to solve the last game his father gave him, flipping rectangles. The game consists of a rectangular board with white and black squares, and Santi's goal is to turn all the squares white. To do this, he can make moves of the following type: He selects a square on the board and flips all the squares in the subrectangle that has as its top-left corner the one Santi has chosen and as its bottom-right corner the bottom-right square of the board (flipping any square that is in the same row as the one he has chosen or lower and in the same column as the one he has chosen or further to the right). Since Santi wants to get back to riding his horse as soon as possible, he wants to solve the game in the minimum number of moves possible, and he asks for your help.

Note: Flipping a square means changing its color. That is, if it was white, it becomes black and vice versa.

Example of a move to understand the dynamics of the game:

If Santi has the board

1 0 1

1 1 0

and selects the bold square, the result will be as follows, with the squares that have changed marked in italics:

1 1 0

1 0 1

Input

The input starts with an integer $$$t$$$, the number of cases. It is followed by the $$$t$$$ cases, each described by two integers $$$n$$$, $$$m$$$ (the dimensions of the board) and $$$n$$$ rows with $$$m$$$ numbers each, separated by spaces. These numbers describe the board and can be $$$0$$$ if the initial square is white or $$$1$$$ if the initial square is black.

Output

Print $$$t$$$ lines, each with a single integer, the minimum number of moves that Santi needs to solve the game.

Scoring

$$$1 \leq t \leq 40$$$

19 Points $$$ 1 \leq n, m \leq 5 $$$

27 Points $$$ 1 \leq n, m \leq 80 $$$

8 Points $$$ n = 1, 1 \leq m \leq 1000$$$

16 Points $$$ 1 \leq n, m \leq 1000 $$$ and the initial board is painted like a chessboard, alternating the colors white and black so that there are no two adjacent squares of the same color (as in the last example)

30 Points $$$ 1 \leq n, m \leq 1000 $$$

Example
Input
3
2 3
1 0 1
1 1 0
4 2
0 0
0 1
1 0
1 1
5 5
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
Output
4
3
9