405230: GYM101853 E Maximum Sum

You are given a grid consisting of n rows each of which is dived into n columns. The rows are numbered from 1 to n from top to bottom, and the columns are numbered from 1 to n from left to right. Each cell is identified by a pair (x, y), which means that the cell is located in the row x and column y. All cells in the grid contain positive integers.

Your task is to choose a subset of the grid's cells, such that their summation is as maximal as possible, and there are no two adjacent cells in that subset. Two cells are considered adjacent if they are horizontal, vertical, or diagonal neighbors.

The first line contains an integer T (1 ≤ T ≤ 100), in which T is the number of test cases.

The first line contains an integer n (1 ≤ n ≤ 16), in which n is the number of rows and columns in the grid.

Then n lines follow, each line contains n integers, giving the grid. All values in the grid are between 1 and 1000 (inclusive).

For each test case, print a single line containing the maximum sum of a subset of the grid's cells. The chosen subset must not contain any adjacent cells.

2
2
4 7
2 9
3
1 2 3
4 5 6
7 8 9

9
20