Trên bảng \(n \times n\), mỗi ô chứa một số nguyên không vượt quá \(10^9\). Xét trò chơi đối kháng giữa hai người: Trò chơi diễn ra trong \(n\) lượt đi, mỗi lượt người đi trước chọn một hàng, người đi sau chọn một cột. Nếu số \(s\) trong ô giao giữa dòng và cột được chọn là số dương thì người đi trước được cộng \(s\) điểm, người đi sau bị trừ đi \(s\) điểm. Ngược lại, nếu số \(s\) là số âm thì người đi trước bị trừ \(|s|\) điểm, người đi sau được cộng thêm \(|s|\) điểm. Sau lượt đi đó, bảng bị xóa hàng và cột mà hai người chơi vừa chọn. Người có điểm càng cao càng thể hiện sự thông minh của mình.

Yêu cầu

Cho biết cả hai người đều chơi tối ưu, hãy tính điểm lớn nhất có thể của người đi trước.

Input

• Dòng đầu ghi số nguyên \(T\) là số bộ dữ liệu.
• \(T\) nhóm dòng sau, mỗi nhóm dòng có dạng:
  • Dòng đầu của nhóm ghi số \(n\).
  • \(n\) dòng sau, mỗi dòng chứa \(n\) số nguyên mô tả bảng số.

Output

• Gồm \(T\) dòng, mỗi dòng là điểm lớn nhất có thể của người đi trước tương ứng với dữ liệu vào.

Example

3 
2
10 10
-5 -5
2
10 -5
10 -5
2
10 -5
-5 10

5 
5 
-10

Constraints

• \(T \le 10\).
• Các giá trị trong bảng không vượt quá \(10^9\).
• Subtask \(1\) (\(30\%\) số điểm): \(n \le 8\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 16\).
• Subtask \(3\) (\(40\%\) số điểm): \(n \le 200\).

Nguồn: 3D'21