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 ô \((i,\ j)\) giao giữa
dòng \(i\) và cột \(j\) đượ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ố 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
\(i\) và cột \(j\) 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.

Dữ liệu vào:

- 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\ \leq \ 16)\);

• \(n\) dòng sau, mỗi dòng chứa số \(n\) nguyên mô tả bảng số.

Kết quả:

- 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.

Ví dụ: