Cho một hình vuông A gồm n×n ô vuông, trên mỗi ô vuông chứa 1 số nguyên(n≤1000), các dòng được đánh số trên xuống dưới bắt đầu từ 1, các cột được đánh số từ trái qua phải cũng bắt đầu từ 1. Mỗi số trong bảng có giá trị tuyệt đối không vượt quá 10000. Đường chéo chính của bảng là đường thẳng nối hai ô (1,1) và(n,n). Một bảng được gọi là đối xứng nếu lấy các phần tử trên đường chéo chính làm trục đối xứng, các phần tử nằm về 2 phía của trục đối xứng tương ứng bằng nhau.

Yêu cầu: Hãy kiểm tra xem một bảng hình vuông cho trước có đối xứng hay không.

Dữ liệu vào:

• Dòng đầu chứa số n.
• Dòng thứ i trong n dòng tiếp theo chứa n số nguyên lần lượt ứng với các phần tử nằm trên dòng thứ i của bảng A.

Dữ liệu ra:

• Nếu bảng trên đối xứng thì ghi 1, ngược lại ghi 0.

Ví dụ

Input

5
1 2 3 1 9
2 2 6 7 6
3 6 3 8 12
1 7 8 1 3
9 6 12 3 4

Output

1

Trên đây là một ví dụ về hình vuông đối xứng