Sức mạnh tối thiểu của phù thủy

Harry Potter phải băng qua một hầm ma thuật hình chữ nhật gồm \(R\) hàng và \(C\) cột. Mỗi ô \((i, j)\) chứa một số nguyên \(S[i][j]\):

• nếu \(S[i][j] < 0\), ô đó có một con rồng và Harry bị mất \(|S[i][j]|\) sức mạnh;
• nếu \(S[i][j] \ge 0\), ô đó có bình thuốc và Harry được cộng thêm \(S[i][j]\) sức mạnh.

Harry xuất phát tại ô \((1,1)\) (góc trên trái) và cần đến ô \((R, C)\) (góc dưới phải), mỗi bước chỉ được đi xuống ô \((i+1, j)\) hoặc sang phải ô \((i, j+1)\). Sức mạnh của Harry phải luôn dương (lớn hơn \(0\)) sau khi xử lý từng ô trên đường đi, kể cả ô đích; nếu bằng \(0\) hoặc âm thì Harry thất bại.

Hãy tìm sức mạnh khởi đầu nhỏ nhất (một số nguyên dương) để Harry có thể đi đến ô \((R,C)\).

Input

• Dòng đầu chứa số bộ test \(T\).
• Với mỗi bộ test: dòng đầu chứa \(R\) và \(C\), tiếp theo là \(R\) dòng, mỗi dòng gồm \(C\) số nguyên mô tả lưới.

Output

• Với mỗi bộ test in ra một dòng: sức mạnh khởi đầu nhỏ nhất.

Constraints

• \(1 \le T \le 5\)
• \(2 \le R, C \le 500\)
• \(-1000 \le S[i][j] \le 1000\)
• \(S[1][1] = S[R][C] = 0\)

Sample Input

3
2 3
0 -2 3
-4 1 0
2 2
0 5
-1 0
3 4
0 -3 1 2
2 -1 -2 0
-1 4 -3 0

Sample Output

3
1
1

Explanation

Ở bộ test đầu tiên, đường đi \(0 \to -2 \to 1 \to 0\) đòi hỏi sức mạnh khởi đầu ít nhất \(3\) (sau ô \(-2\) phải còn dương), còn đường còn lại cần \(5\). Ở bộ test thứ hai, đi qua ô \(5\) rồi \(0\) thì chỉ cần sức mạnh \(1\).