Diagonal Sum of a Square Matrix

You are given an \( n \times n \) square matrix. Your task is to compute the sum of the elements along its two main diagonals.

The primary diagonal consists of the elements \( a_{i,i} \) for \( i = 0, 1, \dots, n-1 \), and the secondary diagonal consists of the elements \( a_{i, n-i-1} \) for \( i = 0, 1, \dots, n-1 \). Note that if \( n \) is odd, the center element will be counted twice.

For example, given the matrix:

[ \begin{bmatrix} 1 & 2 & 3 \ 4 & 5 & 6 \ 7 & 8 & 9 \end{bmatrix} ]

The primary diagonal sum is \(1+5+9=15\) and the secondary diagonal sum is \(3+5+7=15\), so the total sum is \(15+15=30\).

inputFormat

The input is given via standard input. The first line contains an integer \( T \), representing the number of test cases. Each test case starts with an integer \( n \) indicating the size of the \( n \times n \) matrix, followed by \( n \) lines each containing \( n \) space-separated integers.

For example:

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

outputFormat

For each test case, output the total sum of the two diagonals on a separate line via standard output.

For the sample input above, the output should be:

30
10
10

## sample

1
3
1 2 3
4 5 6
7 8 9

30