题目描述

F 市有一个商业用地块，这个地块分为 N*N 的单位面积的正方形，每个单位面积都有一个参考收益（收益都是非负数）。

市长想找两个开发商共同开发这个地块。首先，两方的划定的必须是矩形区域，同时规定两个矩形区域相邻，且只有一个交点。最后为了体现公平避免纠纷，两个区域的参考收益应该相当。

请问划定这样的两个区域有多少种方案？

输入格式

第一行一个整数N，表示整个地块的大小为 N*N 。

接下来 N 行，每行 N 个整数 $A_{i,j}$ ，表示第 i 行第 j 列的单位面积的参考收益。

数据范围

40% 的数据， N <= 10 。

100% 的数据，N <= 50 , 0 < $A_{i,j}$ < 1000 。

输出格式

一个整数，代表符合划定规则的方案数。

样例

3
1 2 3
4 5 6
7 8 9

2

样例解释