#### Maximum Score

You are given **N** integer sequences **A _{1}, A_{2}, …, A_{N}**. Each of these sequences contains

**N**elements. You should pick

**N**elements, each from one sequence; let’s denote the element picked from sequence

**A**by

_{i}**E**. For each

_{i}**i**(2 ≤

**i**≤

**N**),

**E**should be strictly greater than

_{i}**E**.

_{i-1}Compute the maximum possible value of **E _{1} + E_{2} + … + E_{N}**. If it’s impossible to pick the elements

**E**, print -1 instead.

_{1}, E_{2}, …, E_{N}### Input

- The first line of the input contains a single integer
**T**denoting the number of test cases. The description of**T**test cases follows. - The first line of each test case contains a single integer
**N**. **N**lines follow. For each valid**i**, the**i**-th of these lines contains**N**space-separated integers**A**denoting the elements of the sequence_{i1}, A_{i2}, …, A_{iN}**A**._{i}

### Output

For each test case, print a single line containing one integer — the maximum sum of picked elements.

### Constraints

- 1 ≤
**T**≤ 10 - 1 ≤
**N**≤ 700 - 1 ≤ sum of
**N**in all test-cases ≤ 3700 - 1 ≤
**A**≤ 10_{ij}^{9}for each valid**i**,**j**

### Subtasks

**Subtask #1 (18 points):** 1 ≤ **A _{ij}** ≤

**N**for each valid

**i**,

**j**

**Subtask #2 (82 points):** original constraints

### Example

Input:1 3 1 2 3 4 5 6 7 8 9Output:18

### Explanation

**Example case 1:** To maximise the score, pick 3 from the first row, 6 from the second row and 9 from the third row. The resulting sum is **E _{1}+E_{2}+E_{3}** = 3+6+9 = 18.

### Solution

Working on the solution.