Returning to Farming

Two people are moving from the city to a friend's square farm. The farm has size N x N and is divided into 1 x 1 cells. The profit of cell (i, j) is Aij, and this value may be negative.

The friend will lend each person one non-empty rectangular part of the farm. Each rectangle must have sides parallel to the grid lines.

The friend wants the two rectangles to have the same total profit. To encourage competition without letting the two areas share an edge, the two rectangles must meet at exactly one corner point. They must not overlap or share an edge segment.

Count the number of unordered ways to choose the two rectangles. Swapping the two people does not make a new way.

The first line contains the size of the farm, N (1 <= N <= 50).

Each of the next N lines contains N integers. The j-th integer on the i-th line is Aij, the profit of cell (i, j) (-1000 < Aij < 1000).

Print the number of ways to lend two rectangles satisfying the conditions.

For the first visible test, the possible pairs are as follows, using zero-based cell coordinates and inclusive rectangle endpoints.

• (0,0)-(1,1) and (2,2)-(2,2)
• (1,0)-(1,0) and (0,1)-(0,1)
• (2,0)-(2,0) and (1,1)-(1,1)
• (1,1)-(1,1) and (0,2)-(0,2)
• (2,1)-(2,1) and (1,2)-(1,2)
• (2,0)-(2,1) and (0,2)-(1,2)
• (1,0)-(2,0) and (0,1)-(0,2)