Description

小明和小花知道学信息学竞赛的学生特别擅长做一些和矩阵相关的问题。例如，同学经常做的一个题目，给你一个 N × M 的矩阵，矩阵里面每个格子上都有一个数，要从左上角 (1,1)，走到右下角 (N, M)，每一步只能往下或者往右走，让你求经过的路径上数的总和最小。小明和小花发现这个问题太简单了，根本难不倒广大的 OIer。于是，他们开始别出心裁了。
他们想着现在给你一个 01 矩阵（即里面每个格子上的数是 0 或者 1），仍旧让你从 (1,1) 走到 (N, M)，每次只能往下面一个格子或者右边一个格子走。定义一条好路径是从起点到终点只经过 0 的格子。但是现在由于 1 的格子太多，所以可能无法完成这个任务。
于是，他们想出了修改操作，对于每个修改操作 (x1, y1)(x2, y2)，表示把以 (x1, y1)为左上角，以 (x2, y2) 为右下角的子矩阵里面每个格子里面的数进行反转，即 0 变成1，1 变成 0。
问题是：最少需要多少次操作，才能使得这个矩阵存在好路径。现在请你来计算。

Input Format

输入的第一行是一个正整数 T，表示矩阵的个数。
对于每个矩阵：
输入第一行是 2 个正整数 N 和 M，表示矩阵的行数和列数。
接下来输入 N 行，每行有 M 个数，都是 0 或者 1，空格隔开。

Output Format

输出 T 个非负整数，每行一个数，表示最少需要的操作数，使得对应矩阵存在好

1
3 3
0 1 1
0 1 0
1 1 0

1

Hint

【输入输出样例 2】

matrix.in	matrix.out
1 5 5 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0	4

【输入输出样例 3】

matrix.in

matrix.out

2 10 10 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 10 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1

1 1

【数据范围】

对于所有的数据 1 ≤ T ≤ 20, 1 ≤ N, M ≤ 10^3。

数据编号	数据范围	特殊性质
1∼3	N, M ≤ 3	无
4∼5	N, M ≤ 12	保证每个矩阵最多只需要 1 次操作
6∼10	T ≤ 2, N, M ≤ 10^3	无

Source

动态规划