Because of necessary software maintenance, Jutge.org may not work well on the afternoons of the 20th and 21th of april.

Control C401A P64789

Statement

html

Your task is to write a program that reads a sequence of square matrices of integers, and for each one prints the sum of the numbers which are in their two diagonals.

Usign the definition

typedef vector<vector<int> > Matrix;

your program must implement and use the function

int sum_diagonals(const Matrix& mat);

that returns the sum of the numbers in the diagonals of the square matrix and non empty |mat|.

Input

The input consists of a sequence of cases. Each case starts with the size n ≥ 1 of the matrix, followed by n lines, each one with the n integers of the corresponding row.

Output

For each matrix, print a line with the sum of the numbers which are in its diagonals.

Public test cases

Input

1
7

2
1 2
3 4

3
 1   3   0
 5   2   7
-8  -4  -9

4
1000000          3          4   -1000000
      1   -1000000    1000000          7
      2   -1000000    1000000          8
1000000          5          6   -1000000

Output

Input

5
11 22 33 46 15
41 33 94 58 71
56 23 45 98 21
54 15 37 26 17
65 88 99 66 11

Output

Information

Author: Professorat de P1
Language: English
Translator: Carlos Molina
Original language: Catalan
Other languages: Catalan
Official solutions: C++
User solutions: C++