Sau thất bại trong vai trò huấn luyện viên của Mirko và nỗi ám ảnh thoáng qua với các món ngon từ thịt của Croatia, vấn đề cân nặng đã thúc đẩy anh làm việc chăm chỉ như một nông dân. Anh ấy đã chuyển đến ngôi làng nơi người bạn Slavko của anh ấy sống. Những người nông dân trong làng chia sẻ một mảnh đất chung rộng lớn có hình vuông ~N×N~, được chia thành các ô vuông đơn vị ~N^2~. Một hình vuông đơn vị tại tọa độ ~(i, j)~ mang lại thu nhập cho Aij, có thể âm (ví dụ: nếu hình vuông phải được duy trì nhưng không được trồng trọt). Người nông dân luôn chia đất chung thành những thửa ruộng hình chữ nhật nhỏ hơn có các cạnh song song với mép đất chung.

Slavko nghi ngờ Mirko kể từ khi anh thất bại trên cương vị huấn luyện viên nên nhất quyết yêu cầu cả hai được giao đất với tổng thu nhập như nhau, nhưng đồng thời hai mảnh đất có chung một góc để hai người bạn cùng trông chừng nhau. người khác (Slavko biết Mirko rất nghịch ngợm). Góc chung phải là điểm duy nhất mà hai lô đất gặp nhau, nhằm tránh những tranh cãi liên quan đến biên giới.

Bạn được cung cấp một mô tả về lô đất chung. Tìm tổng số cặp cốt truyện thỏa mãn tiêu chí của Slavko.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 50)~ là kích thước của thửa đất chung.
• Mỗi dòng trong số ~N~ dòng tiếp theo chứa ~N~ số ~A_{ij}~ ~(-1000 < A_{ij} < 1000)~, thu nhập do ô tương ứng cung cấp.

Output

• Dòng đầu tiên và duy nhất của đầu ra phải chứa tổng số cặp ô thỏa mãn điều kiện đã cho.

Scoring

• Trong dữ liệu kiểm tra có giá trị ít nhất 40% tổng số điểm, ~N~ sẽ tối đa là ~10~.

Sample Input 1

3
1 2 3
2 3 4
3 4 8

Sample Output 1

7

Sample Input 2

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

Sample Output 2

10

Sample Input 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

Sample Output 3

36

Làm rõ ví dụ đầu tiên:

Các cặp hình chữ nhật có thể có là: (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).