说明

gsy 是一个魔法师，她的专业技能就是布置魔法阵

有一个商人想请 gsy 在自己家里构建魔法阵用来防止小偷进入

而这位商人非常有钱，他购买了很多很多的魔法材料，因为他买的实在是太多了

于是他让仆人把魔法材料全部摊在自家院子里，当然，为了防止魔法材料之间互相产生影响，每份魔法材料之间都有一定的间隔

所以我们可以把院子看做是一个 n * n 大小的网格，每个网格中都存放有一份魔法材料

gsy 清晰的感知出了每份魔法材料所拥有的魔法能量，因为 gsy 非常专业

所以就算是极其细微的差别她也能感受到，所以每份魔法材料的能量都是不同的

为了方便 gsy 计算， gsy 将所有的魔法材料按照能量值大小从小到大，从 1 开始进行了编号

因为魔法材料实在是太多了，用所有魔法材料构造一个魔法阵的难度实在是太高了

于是 gsy 有了一个新的思路，她决定以数量代替质量！

所以她决定尽可能多的布置最简易的 `矩形魔法阵`

gsy 的 `矩形魔法阵` 的构造有以下两个要求：
1. 需要使用四份魔法材料作为魔法阵的四个顶点，这四份魔法材料依次相连构成一个和网格轴线对齐的矩形（长宽不要求相等）
2. 因为魔法材料能量一定不同，所以四份魔法材料可以分为两份低能量的魔法材料和两份高能量的魔法材料，在刻画魔法阵时，gsy 会用一条魔力通道将两份低能量的魔法材料连通，再用另一条一条魔力通道将两份高能量的魔法材料连通，保证这两条魔力通道不能交叉

例如如下一个 3 * 3 大小的院子
```cpp
3 1 4
2 5 8
6 9 7
```
比如选择 `2 3 4 8`, `1 4 5 8`, `2 5 6 9` 均可以构成一个矩形魔法阵

现在 gsy 想知道，院子里的材料可以刻画多少`矩形魔法阵`？

这里我们认为:
1. gsy 不会去移动任何魔法材料
2. 一份魔法材料可以同时作为多个矩形魔法阵的顶点，材料本身的能量不会发生改变

输入格式

一个整数 n 表示院子大小

接下来 n 行每行包含 n 个整数，分别表示每份魔法材料的魔法能量值

对于 30% 的数据，n <= 50

对于 60% 的数据，n <= 300

对于 100% 的数据，n <= 1500

输出格式

输出 gsy 最多能刻画的矩形魔法阵的数量

样例

3
3 1 4
2 5 8
6 9 7

7