Submatrix Pairs with One Common Vertex and Equal Sum

Given an \( n \times n \) matrix, your task is to count the number of pairs of submatrices that satisfy the following conditions:

• The two submatrices share exactly one common vertex (i.e. they have exactly one common corner point, and no more).
• The sum of all elements within both submatrices is equal.

A submatrix is defined as any contiguous rectangular block of the matrix. Specifically, a submatrix can be defined by its top-left and bottom-right coordinates \( (r_1, c_1) \) and \( (r_2, c_2) \) (with \( 0 \leq r_1 \leq r_2 < n \) and \( 0 \leq c_1 \leq c_2 < n \)). Its four vertices are \( (r_1, c_1) \), \( (r_1, c_2) \), \( (r_2, c_1) \), and \( (r_2, c_2) \). Two submatrices are considered to have a common vertex if the intersection of their vertex sets is exactly one point.

Please refer to Sample Case 1 for an illustrative example.

inputFormat

The first line contains an integer \( n \) (\(1 \leq n \leq 10\)), representing the size of the matrix.

The next \( n \) lines each contain \( n \) space-separated integers, representing the elements of the matrix.

outputFormat

Output a single integer, the number of pairs of submatrices that have exactly one common vertex and whose sums are equal.

sample

1
5

0