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.
## Input
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).
## Output
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.
[samples]
**Definitions**
Let $ a, b, c, h \in \mathbb{Z}_{\geq 0} $ be the damage values of Alpha, Beta, Charlie variations and Lavos’s health, respectively.
Let $ p \in \{R, N, E\}^* $ be Lavos’s attack pattern of length $ m = |p| $.
Let $ t \in \{A, B, C\}^* $ be the Omnislash sequence of length $ n = |t| $, with $ n \leq m $.
Define a mapping $ \sigma: \{R, N, E\} \to \{a, b, c\} $:
- $ \sigma(R) = a $,
- $ \sigma(N) = b $,
- $ \sigma(E) = c $.
Define a mapping $ \tau: \{A, B, C\} \to \{a, b, c\} $:
- $ \tau(A) = a $,
- $ \tau(B) = b $,
- $ \tau(C) = c $.
**Constraints**
1. $ 0 \leq a, b, c \leq 10^9 $
2. $ 1 \leq h \leq 10^9 $
3. $ 1 \leq |p| \leq 2 \times 10^5 $
4. $ 1 \leq |t| \leq |p| $
**Objective**
Let $ k \in \{0, 1, \dots, m - 1\} $ be the initial offset of Lavos’s pattern, chosen uniformly at random.
For each $ k $, define the total damage dealt during Omnislash as:
$$
D_k = \sum_{i=0}^{n-1} \tau(t[i]) \cdot \mathbf{1}_{\tau(t[i]) = \sigma(p[(k+i) \bmod m])}
$$
Lavos is defeated if $ D_k \geq h $.
Compute the probability:
$$
\mathbb{P} = \frac{1}{m} \cdot \left| \left\{ k \in \{0, \dots, m-1\} \mid D_k \geq h \right\} \right|
$$
Output $ \frac{p}{q} $ as an irreducible fraction.