시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB105350.000%

문제

กาลครั้งหนึ่งมีทุ่งดอกไม้สีชมพูแห่งหนึ่งขนาด N x M ตารางเมตร ในแต่ละตารางเมตรมีดอกไม้อยู่ aij ดอก ทุกๆเช้าฝูงกระต่ายจะมาเก็บดอกไม้เหล่านี้กลับไปกินเพื่อให้ขนของพวกมันมีสีชมพู โดยกระต่ายแต่ละตัวจะเดินจากซ้ายบน ไปขวาล่าง และจะไม่เดินกลับไปทางด้านซ้ายหรือกลับขึ้นด้านบนเด็ดขาด ส าหรับทุกๆตารางเมตรที่เดินผ่านและยังมีดอกไม้อยู่กระต่ายจะเก็บดอกไม้ 1 ดอก ถามว่าต้องใช้กระต่ายอย่างน้อยกี่ตัวจึงจะเก็บดอกไม้ได้ทั้งหมด

입력

บรรทัดแรกเป็นจ านวนกรณีทดสอบ T ชุด (1 ≤ T ≤ 10) กรณีทดสอบแต่ชุดประกอบด้วยข้อมูลดังนี้

  • บรรทัดแรก เป็นจ านวนแถวและคอลัมน์ของทุ่งหญ้า N และ M ตามล าดับ (1 < N, M ≤ 1 600)
  • บรรทัดที่ 2 ถึง N+1 ประกอบด้วยจ านวนเต็ม M จ านวน โดยแต่ละจ านวน aij แสดงจ านวน ดอกไม้ในตารางเมตรนั้น (0 ≤ aij ≤ 100)

출력

ส าหรับแต่ละกรณีทดสอบ ให้แสดงจ านวนกระต่ายที่น้อยที่สุดที่ใช้ในการเก็บดอกไม้ทั้งหมด

예제 입력 1

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

예제 출력 1

4
8
11