Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Kì nghỉ hè, Tôm và Bống về nhà bà ngoại chơi. Khu vườn nhà bà ngoại rất rộng và có rất nhiều cây cam, được trồng thẳng hàng đều tăm tắm. Cả Tôm và Bống đều đòi “xí phần” những cây cam của mình. Bà ngoại rất chiều các cháu, để cho 2 đứa khỏi cãi nhau, bà ngoại quyết định cho mỗi đứa hẳn một mảnh vườn con hình chữ nhật và yêu cầu mỗi đứa phải chăm sóc tất cả những cây cam trong mùa hè này. Để công bằng hơn, số lượng quả cam trong khu vườn nhỏ của Tôm và Bống sẽ bằng nhau.

Ngay sau đó, Tôm và Bống đã đi đếm xem mỗi cây cam trong vườn có bao nhiêu quả. Một vấn đề đặt ra là lấy gì để làm ranh giới bây giờ. Tôm và Bống đi tìm khắp nhà bà ngoại nhưng chỉ tìm được 3 cái cọc. Bà ngoại bảo rằng thế này thì 2 khu vườn nhỏ của hai đứa phải có 1 điểm chung (và là duy nhất). Chỗ này chính là chỗ để một chiếc cọc cột mốc trung gian, 2 chiếc cọc còn lại, mỗi chiếc sẽ giới hạn khu vườn của mỗi đứa.

Các bạn hãy giúp bà ngoại của Tôm và Bống xem có bao nhiêu cách chọn ra khu vườn con cho hai bạn nhỏ nhé!

Input

Dòng đầu tiên số nguyên n (n <= 50), giới hạn của khu vườn. Khu vườn có kích thước n x n.

N dòng tiếp theo, mỗi dòng gồm n số. Mỗi số a[i][j] (có trị tuyệt đối nhỏ hơn 1000) cho biết cây cam tại ô (i, j) trong vườn có a[i][j] quả.

Output

In ra số cặp mảnh đất hình chữ nhật thỏa mãn điều kiện của đề bài (có duy nhất một đỉnh chung và số lượng quả cam của 2 mảnh đất phải bằng nhau).

Example

Test 1:

Input:

3
1 2 3
2 3 4
3 4 8

Output:

7

Giải thích test 1:

(0,0)-(1,1) và (2,2)-(2,2);
(1,0)-(1,0) và (0,1)-(0,1);
(2,0)-(2,0) và (1,1)-(1,1);
(1,1)-(1,1) và (0,2)-(0,2),
(2,1)-(2,1) và (1,2)-(1,2);
(2,0)-(2,1) và (0,2)-(1,2);
(1,0)-(2,0) và (0,1)-(0,2).

Test 2:

Input:

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

Output:

10

Test 3:

Input:

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

Output:

36