P5038 [SCOI2012] Strange Game

Blinker has recently become interested in a strange game. The game is played on an $N \times M$ board, and each cell contains a number. Each time, Blinker chooses two adjacent cells and increases both numbers by $1$. Now Blinker wants to know the minimum number of moves needed to make all numbers on the board become the same. If it can never become the same, output $-1$.

The first line contains an integer $T$, meaning the input consists of $T$ rounds of the game. In each round, the first line contains two integers $N$ and $M$, representing the number of rows and columns of the board. Then follow $N$ lines, each containing $M$ numbers.

For each round, output the minimum number of moves needed to finish the game. If it can never become the same number, output $-1$.

For $30\%$ of the testdata, it is guaranteed that $T \le 10$ and $1 \le N, M \le 8$. For $100\%$ of the testdata, it is guaranteed that $T \le 10$ and $1 \le N, M \le 40$. All numbers are positive integers and less than $10^9$. Translated by ChatGPT 5