Cho một khối lập phương kích thước ~n~ chia làm ~n^{3}~ khối lập phương đơn vị. Mỗi khối lập phương đơn vị chứa ~1~ số nguyên.

Bạn hãy tìm một khối lập phương con của khối lập phương đã cho sao cho tổng các số trong khối lập phương con đó là lớn nhất.

Input

• Dòng đầu: số lượng test.
• Tiếp theo là các test, mỗi test gồm: dòng đầu là ~n~. Sau đó ~n~ nhóm dòng thể hiện lớp cắt của hình lập phương nhìn từ mặt trước từ gần ra xa, mỗi nhóm gồm ~n~ dòng, mỗi dòng gồm ~n~ số liệt kê các số trên lớp cắt từ trên xuống dưới, trái qua phải.

Chú ý: ~n \leq 30~. Giá trị của khối lập phương đơn vị thuộc kiểu integer.

Output

• Mỗi dòng chứa tổng của khối lập phương con lớn nhất của test tương ứng.

Sample Input

2
3
0 -1 3
-5 7 4
-8 9 1
-1 -3 -1
2 -1 5
0 -1 3
3 1 -1
1 3 2
1 -2 1
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

Sample Output

27
64