Cho ma trận kích thước ~n \times n~ ô, mỗi ô chứa giá trị nguyên ~a_{i,j}~. Hãy lập trình đếm xem bao nhiêu cặp ma trận con ~<A, B>~ sao cho:

• Có tổng các giá trị trong ma trận ~A~ bằng tổng các giá trị của ma trận ~B~.

• Hai ma trận ~A~ và ~B~ không chồng lên nhau và có duy nhất một một góc chung với nhau (xem hình vẽ của testcase mẫu số 1)

Input

Dòng thứ nhất chứa số nguyên là ~n~ thỏa ~1 \le n \le 50~.

~n~ dòng tiếp theo, mỗi dòng chứa các phần tử ~a_{i,j}~ của ma trận, thỏa ~-1000 \le a_{i,j} \le 1000~.

Output

In ra số cặp cần tìm.

Samples

Sample Input 1

3
1 2 3
2 3 4
3 4 8

Sample Output 1

7

Sample Input 2

4
31 43 23 31
45 32 32 31
32 23 33 35
34 54 14 23

Sample Output 2

4

Note

Các cách chia của testcase 1 như sau: