Cho một bảng kích thước ~n \times m~. Ban đầu, tất cả các ô trên bảng đều có giá trị bằng ~0~. Ta có thể thực hiện các thao tác sau:

• Đặt một viên gạch hình chữ nhật kích thước ~1 \times k~ (ngang) hoặc ~k \times 1~ (dọc), với ~k~ là số nguyên dương bất kỳ, lên trên bảng.

Mỗi lần đặt một viên gạch, giá trị của tất cả các ô mà viên gạch che phủ sẽ tăng lên đúng ~1~.

Hãy xác định số lượng viên gạch ít nhất cần đặt sao cho sau cùng, giá trị tại mỗi ô ~(i,j)~ trên bảng đúng bằng ~a_{i,j}~.

Input

Mỗi bộ dữ liệu gồm nhiều test case. Dòng đầu tiên chứa số lượng test case ~t~ (~1 \le t \le 1000~). Phần mô tả các test case như sau.

Dòng đầu tiên của mỗi test case là hai số nguyên dương ~n~ và ~m~ (~1 \le n, m \le 50~).

Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa ~m~ số nguyên ~a_{i, 1}, a_{i, 2}, \dots, a_{i, m}~ (~0 \le a_{i, j} \le 10^9~).

Đảm bảo rằng tổng của ~nm~ ở mỗi bộ test không vượt quá ~3000~.

Output

Với mỗi test case, in ra một số nguyên duy nhất là số viên gạch ít nhất cần đặt.

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