Cảm ơn rất nhiều vì đã giúp Harry Potter tìm ra Hòn đá bất tử vào tháng \(10\). Chúng tôi đã không nói với bạn rằng đó chỉ là một trò chơi trực tuyến thôi sao? Nhưng không, đây là nhiệm vụ thực sự dành cho Harry. Bạn được cung cấp một lưới ma thuật \(S\) có \(R\) hàng và \(C\) cột. Mỗi ô trong lưới này có thể chứa một con rồng hoặc một lọ thuốc ma thuật. Con rồng sẽ lấy đi sức mạnh của Harry, còn lọ thuốc sẽ giúp tăng thêm sức mạnh. Nếu sức mạnh của Harry giảm xuống \(0\) hoặc thấp hơn tại bất kỳ thời điểm nào trong cuộc hành trình, anh ta sẽ chết và không có cách nào hồi sinh.

Harry bắt đầu hành trình tại ô góc trên bên trái \((1, 1)\) và Hòn đá phù thủy nằm tại ô góc dưới bên phải \((R, C)\). Từ mỗi ô, Harry chỉ được phép di chuyển xuống dưới hoặc sang phải. Anh ta không được phép ra khỏi lưới ma thuật. Hãy giúp Harry xác định sức mạnh tối thiểu mà anh ta cần phải có từ lúc bắt đầu để có thể sống sót đến được Hòn đá phù thủy.

Dữ liệu vào

• Dòng đầu tiên chứa số lượng bài kiểm tra \(T\).
• Tiếp theo là \(T\) bộ dữ liệu. Mỗi bộ bao gồm:
  • Một dòng chứa số \(R\) và \(C\) (số hàng và số cột của lưới).
  • \(R\) dòng tiếp theo, mỗi dòng gồm \(C\) số nguyên, biểu thị sức mạnh tại các ô trong lưới.
  • Nếu giá trị tại ô là số âm, ô đó chứa rồng và giá trị này sẽ làm giảm sức mạnh của Harry.
  • Nếu giá trị là số dương, ô đó chứa thuốc ma thuật và sẽ tăng sức mạnh cho Harry.

Dữ liệu ra

• Với mỗi bài kiểm tra, in ra một dòng chứa sức mạnh tối thiểu Harry cần mang theo để bắt đầu tại ô \((1, 1)\) và đảm bảo sức mạnh của anh luôn lớn hơn 0 trong suốt hành trình đến ô \((R, C)\).

Ràng buộc

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

Input 1

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

Output 1

2
1
2