题目描述

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

这个游戏在一个 $n\times 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\leq 10$，$1\leq n,m\leq 8$。
对于 $100\%$ 的数据，保证 $T\leq 10$，$1\leq n,m\leq 40$，所有数为正整数且小于 $10^9$。