[SCOI2012] 奇怪的游戏

题目描述

$Blinker$最近喜欢上一个奇怪的游戏。

这个游戏在一个 $N \times M$ 的棋盘上玩，每个格子有一个数。每次$Blinker$会选择两个相邻的格子，并使这两个数都加上$1$。

现在$Blinker$想知道最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同一个数则输出$-1$。

输入格式

输入的第一行是一个整数$T$，表示输入数据有T轮游戏组成。

每轮游戏的第一行有两个整数$N$和$M$， 分别代表棋盘的行数和列数。 接下来有$N$行，每行$M$个数。

输出格式

对于每个游戏输出最少能使游戏结束的次数，如果永远不能变成同一个数则输出$-1$。

样例 #1

样例输入 #1

2 
2 2 
1 2 
2 3 
3 3 
1 2 3 
2 3 4 
4 3 2

样例输出 #1

2 
-1

提示

对于$30$%的数据，保证$T<=10,1<=N,M<=8$

对于$100$%的数据，保证 $T<=10,1<=N,M<=40$，所有数为正整数且小于$1000000000$