Giảm độ cao

Cho một bảng số nguyên $a$ kích thước $n\times m$. Bạn đang đứng ở ô $(1,1)$ và muốn đi tới ô $(n,m)$. Mỗi bước, bạn chỉ có thể đi từ ô $(i,j)$ sang ô $(i+1,j)$ (xuống) hoặc $(i,j+1)$ (sang phải). Ngoài ra có một ràng buộc: nếu giá trị (độ cao) của ô hiện tại bằng $x$ thì ô đi tiếp theo phải có giá trị bằng đúng $x+1$.

Trước khi xuất phát, bạn được phép thực hiện một số thao tác. Mỗi thao tác, bạn chọn một ô bất kỳ $(i,j)$ rồi giảm giá trị của ô đó đi $1$ (tức là gán $a_{i,j}:=a_{i,j}-1$). Giá trị của ô sau khi giảm có thể nhỏ hơn hoặc bằng $0$. Bạn cũng được phép giảm giá trị của ô $(1,1)$.

Hãy tính số thao tác giảm tối thiểu cần thực hiện để tồn tại ít nhất một đường đi hợp lệ từ ô $(1,1)$ tới ô $(n,m)$. Dữ liệu đảm bảo luôn có đáp án.

Bạn phải xử lý $t$ bộ dữ liệu độc lập.

Dữ liệu vào

Dòng đầu chứa một số nguyên $t$ — số bộ dữ liệu.

Với mỗi bộ dữ liệu:

• Dòng đầu chứa hai số nguyên $n$ và $m$ — số dòng và số cột của bảng.
• $n$ dòng tiếp theo, mỗi dòng chứa $m$ số nguyên; số thứ $j$ trên dòng thứ $i$ là $a_{i,j}$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng chứa một số nguyên — số thao tác giảm tối thiểu cần thực hiện.

Ràng buộc

• $1\le t\le 100$
• $1\le n,m\le 100$
• $1\le a_{i,j}\le {10}^{15}$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $100$.
• Tổng $m$ trên tất cả các bộ dữ liệu không vượt quá $100$.

Ví dụ