在 Mirko 担任教练失败并对克罗地亚肉类美食产生短暂的执念之后，他的体重问题促使他开始努力成为一名农民。他搬到了他的朋友 Slavko 居住的村庄。村里的农民们共同拥有一块 $N \times N$ 正方形的大型公共土地，该土地被划分为 $N^2$ 个单位正方形。位于坐标 $(i, j)$ 的单位正方形带来的收益为 $A_{i,j}$，该收益可以为负数（例如，如果该正方形需要维护但未耕作）。农民们总是将公共土地划分为较小的矩形区域，且其边界与公共土地的边界平行。

由于 Mirko 之前当教练失败，Slavko 对他持怀疑态度，因此他坚持要求分配给他们两人的土地必须具有相同的总收益，并且这两个区域恰好共享一个公共角，以便这两个朋友可以互相照看（Slavko 知道 Mirko 容易调皮捣蛋）。为了防止因边界问题产生争执，该公共角必须是这两个区域相交的唯一一点。

给定公共土地的描述，求满足 Slavko 条件的土地对（矩形对）的总数。

输入格式

第一行包含一个正整数 $N$ ($1 \le N \le 50$)，表示公共土地的维度。

接下来的 $N$ 行，每行包含 $N$ 个空格分隔的整数 $A_{i,j}$ ($-1000 < A_{i,j} < 1000$)，表示对应单元格的收益。

输出格式

输出的第一行也是唯一一行，包含满足给定条件的土地对的总数。

数据范围

对于至少 40% 的测试数据，满足 $N \le 10$。

样例

输入样例 1

3
1 2 3
2 3 4
3 4 8

输出样例 1

7

输入样例 2

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

输出样例 2

10

输入样例 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

输出样例 3

36

说明

样例 1 说明：可能的矩形对为： $(0,0)-(1,1)$ 和 $(2,2)-(2,2)$，$(1,0)-(1,0)$ 和 $(0,1)-(0,1)$，$(2,0)-(2,0)$ 和 $(1,1)-(1,1)$，$(1,1)-(1,1)$ 和 $(0,2)-(0,2)$，$(2,1)-(2,1)$ 和 $(1,2)-(1,2)$，$(2,0)-(2,1)$ 和 $(0,2)-(1,2)$，$(1,0)-(2,0)$ 和 $(0,1)-(0,2)$。

注：括号中的第一个数字表示行，第二个数字表示列。