明明买了一块崭新而洁白的地毯，但是拿回家时不小心打翻了一桶黑色的颜料，把地毯污染得一塌糊涂。明明心想：这地毯也不能就这样浪费了，至少再涂一下整得好看一点吧。

            具体地说，这块地毯可以看做一个$n*m$的矩阵，现在地毯上有些格子是黑色的，其他的格子是白色的。明明希望用黑色或者白色的颜料重新涂某些格子，使得每个同色的极大连通块都是矩形，也就是说，涂完之后的地毯看上去是由一块一块矩阵构成的。

            明明十分珍惜他的颜料，所以希望重新涂的格子数越少越好。但是如果重新涂的格子数无论如何都必须大于$k$，那么明明宁愿选择扔掉这块地毯。

            注：如果你不会判定题目中“每个同色极大连通块都是矩形”的条件，那么这里给你一个易于实现的方法：这等价于任意一个边长为2的正方形内黑色和白色的格子的个数均为偶数。

第一行为一个正整数$T$，表示数据组数。
 接下来$T$组数据，每组数据的第一行有三个整数$n,m,k$，表示地毯的大小和最多能够重新涂多少个格子。
 接下来$n$行，每行$m$个整数，1表示该格子为黑色，0则为白色。

对每组数据输出单独的一行，表示最少需要重新涂的格子数，若其大于$k$，则输出-1。

3
5 5 2
1 1 1 1 1
1 1 1 1 1
1 1 0 1 1
1 1 1 1 1
1 1 1 1 1
3 4 1
1 0 0 0
0 1 1 1
1 1 1 0
3 4 1
1 0 0 1
0 1 1 0
1 0 0 1

1
-1
0