Problem Description

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$.

Input Format

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.

Output Format

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

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

2 
-1 

Hint

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