You are given an ~n \times m~ board, where initially all cells on the board have value ~0~. You may perform the following operation:

• Place a rectangular brick of size ~1 \times k~ (horizontal) or ~k \times 1~ (vertical), where ~k~ is any positive integer, on the board.

Each time a brick is placed, the value of every cell covered by that brick increases by exactly ~1~.

Determine the minimum number of bricks that must be placed so that, in the end, the value of each cell ~(i,j)~ on the board is exactly ~a_{i,j}~.

Input

Each dataset consists of multiple test cases. The first line contains the number of test cases ~t~ (~1 \le t \le 1000~). The description of the test cases follows.

The first line of each test case contains two positive integers ~n~ and ~m~ (~1 \le n, m \le 50~).

The ~i~-th of the next ~n~ lines contains ~m~ integers ~a_{i, 1}, a_{i, 2}, \dots, a_{i, m}~ (~0 \le a_{i, j} \le 10^9~).

It is guaranteed that the total value of ~nm~ over each dataset does not exceed ~3000~.

Output

For each test case, print a single integer: the minimum number of bricks that must be placed.

Scoring

Sample Input 1

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

Sample Output 1

4
3
2