Problem Description

Given an $n \times n$ matrix, determine how many pairs of submatrices have exactly one common vertex and equal sums of elements.

Note that a common vertex refers to the intersection of vertices, not the existence of a common cell. Refer to Sample Input 1 to understand the meaning of "common vertex".

Input Format

The first line of input contains a positive integer $n$.

The next $n$ lines each contain $n$ integers, representing the matrix $a_{i,j}$, which may include negative numbers.

Output Format

Output a single line containing the number of valid pairs of submatrices.

Sample Input and Output

Sample Input #1

3
1 2 3
2 3 4
3 4 8

Sample Output #1

7

Sample Input #2

4
-1 -1 -1 -1
1 2 3 4
1 2 3 4
1 2 3 4

Sample Output #2

10

Sample Input #3

5
-1 -1 -1 -1 -1
-2 -2 -2 -2 -2
-3 -3 -3 -3 -3
-4 -4 -4 -4 -4
-5 -5 -5 -5 -5

Sample Output #3

36

Notes

Data Range

• For $40\%$ of the data, $1 \le n \le 10$.
• For $100\%$ of the data, $1 \le n \le 50$ and $-1000 \le a_{i,j} \le 1000$.

Sample 1 Explanation

Possible pairs of rectangles are:

• $(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)$.

There are a total of $7$ pairs, so the output is $7$.

This problem is translated from COCI2013-2014 CONTEST #1 T3 RATAR.

$\mathtt{Subtask \ 0}$ is the sample data. (10 pts)

$\mathtt{Subtask \ 1}$ includes data where $1 \le n \le 10$. (30 pts)

$\mathtt{Subtask \ 2}$ includes data where $1 \le n \le 50$ and $-1000 \le a_{i,j} \le 1000$. Please note the time limit for this subtask. (60 pts)

见题面 Input 部分

见题面 Output 部分