Circle

In the country of Olympia, a school hosts a computer science club consisting of N experienced programmers and N beginners. The club's coach organizes sessions by pairing each experienced programmer with a beginner. After each training session, the coach evaluates the effectiveness of the collaboration between the i-th experienced programmer and the j-th beginner, denoted by the value ( a_ij ). The club's overall effectiveness is calculated as the sum of the effectiveness scores for all N pairs, ensuring that each student is paired with exactly one other student. The coach is interested in knowing whether the club's overall effectiveness remains constant regardless of how the students are paired.

**Task**

Write a program that, given the effectiveness scores for each pair of experienced programmer and beginner, determines whether the club's overall effectiveness is independent of the pairing arrangement.

**Input**

The first line of the input contains a natural number K (1 ≤ K ≤ 50) — the number of test cases. Each test case describes a different club and begins with a line containing a natural number N (2 ≤ N ≤ 100), representing the number of experienced programmers and beginners in the club. This is followed by N lines, each containing N integers separated by spaces. The j-th integer on the i-th line is ( a_ij ), indicating the effectiveness of the i-th experienced programmer working with the j-th beginner, where ( 0 $\le$ a_ij $\le$ 20000 ).

**Output**

For each test case, output a single number on a separate line: the total effectiveness of the club if it is independent of the pairing arrangement, or -1 if it varies depending on the pairing.

**Scoring**

The test set is divided into three blocks with additional constraints:

1. 30% of the points: 2 ≤ N ≤ 10 for all clubs. 2. 20% of the points: 10 < N ≤ 50 for all clubs. 3. 50% of the points: 50 < N ≤ 100 for all clubs.

Examples