Control C401A P64789

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 \ge 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.