After Mirko's failed stint as a coach and a passing obsession with Croatian meat delicacies, his weight

problems have motivated him to work hard as a farmer. He has moved to a village where his friend

Slavko lives. Farmers in the village share a large common plot of land in the shape of a N×N square,

divided into N² unit squares. A unit square at coordinates (i, j) brings in the income of Aij, which can

be negative (for example, if the square has to be maintained but is not cultivated). The farmers always

divide the common land into smaller rectangular fields with edges parallel to the common land

edges.

Slavko is skeptical of Mirko since his failure as a coach, so he insists that both of them are assigned

land with the same total income, but also thet the two plots share exactly one common corner so

that the two friends can keep an eye on each other (Slavko knows that Mirko is prone to mischief). The

common corner must be the only point where the two plots meet, in order to prevent border-related

arguments.

You are given a description of the common land plot. Find the total number of plot pairs that satisfy

Slavko's criteria.

Input

The first line of input contains the positive integer N (1 ≤ N ≤ 50), the dimensions of the common

land plot.

Each of the following N lines contains N space-separated numbers Aij (-1000 < Aij < 1000), the income

provided by the respective cell.

Output

The first and only line of output must contain the total number of plot pairs satisfying the given

condition.

Example

Input:
3

1 2 3

2 3 4

3 4 8

Output:
7