문제

감독으로서의 실패와 크로아티아 육가공 음식에 대한 잠깐의 집착 이후, 체중 문제를 느낀 Mirko는 열심히 농부로 일하기로 결심했다.

그는 친구 Slavko가 사는 마을로 이사했다.

마을의 농부들은 N×N 크기의 큰 공동 농지를 함께 사용한다. 이 농지는 N²개의 단위 정사각형 칸으로 나누어져 있다.

좌표 (i, j)에 있는 칸의 수익은 A[i][j]이며, 이는 음수일 수도 있다. (예를 들어 경작은 하지 않지만 유지 비용이 드는 땅일 수 있다.)

농부들은 항상 공동 농지를 변과 평행한 직사각형 모양의 작은 땅들로 나누어 가진다.

Slavko는 Mirko가 감독 시절 실패했던 일을 아직 의심하고 있기 때문에, 두 사람이 받는 땅의 총 수익이 같아야 한다고 주장한다.

또한 두 사람이 서로를 감시할 수 있도록, 두 직사각형 땅은 정확히 하나의 꼭짓점만 공유해야 한다.

공유하는 그 꼭짓점 외에는 두 땅이 어떤 점에서도 만나서는 안 된다. (경계 분쟁을 막기 위해서다.)

공동 농지의 정보가 주어질 때, 조건을 만족하는 직사각형 땅의 쌍의 개수를 구하여라.

입력

첫째 줄에 농지의 크기 N이 주어진다. (1 ≤ N ≤ 50)

다음 N개의 줄에는 각각 N개의 정수 A[i][j]가 공백으로 구분되어 주어진다. (-1000 < A[i][j] < 1000)

출력

조건을 만족하는 직사각형 땅의 쌍의 총 개수를 출력한다.

예제 입력 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