[SCOI2012]奇怪的游戏

时间限制:40s    【提交】    空间限制:128MB

题目描述

Blinker最近喜欢上一个奇怪的游戏。
这个游戏在一个 N*M 的棋盘上玩,每个格子有一个数。每次 Blinker 会选择两个相邻
的格子,并使这两个数都加上 1。
现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数,如果永远不能变成同
一个数则输出-1。


输入格式

输入的第一行是一个整数T,表示输入数据有T轮游戏组成。
每轮游戏的第一行有两个整数N和M, 分别代表棋盘的行数和列数。
接下来有N行,每行 M个数。 


输出格式


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


样例输入

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

样例输出

2 
-1 

 

提示

【数据范围】
    对于30%的数据,保证  T<=10,1<=N,M<=8
对于100%的数据,保证  T<=10,1<=N,M<=40,所有数为正整数且小于1000000000 
 


题目来源

没有写明来源