[DSA-QuayLui-NhanhCan].Bài toán N quân hậu 2.

Cho một bàn cờ 8 x 8, mỗi ô có một giá trị A[i][j] nhất định (0 ≤ A[i][j] ≤ 100), tương ứng với điểm số đạt được nếu như bạn đặt một quân cờ vào đó. Nhiệm vụ của bạn là đặt 8 quân hậu lên bàn cờ, sao cho không có 2 quân nào ăn nhau, và số điểm đạt được là lớn nhất.

Input Format

Dòng đầu tiên là số lượng bộ test T (T ≤ 20). Mỗi test gồm 8 dòng, mỗi dòng 8 số nguyên mô tả bàn cờ.

Constraints

.

Output Format

Với mỗi test, in ra đáp án trên một dòng.

Ví dụ:

Dữ liệu vào

1
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

Dữ liệu ra

260