Giữa thảo nguyên rộng lớn, một người lữ hành đang trên đường tìm đến ngôi làng nằm ở phía bên kia vùng đất. Tuy nhiên, thảo nguyên không hoàn toàn bằng phẳng mà trải dài với những ngọn đồi, thung lũng và các vùng đất có độ cao khác nhau.

Để lên kế hoạch cho chuyến đi, người lữ hành sử dụng một tấm bản đồ được chia thành ~N * N~ ô vuông. Mỗi ô mang một giá trị nguyên dương biểu thị độ cao của vùng đất tương ứng.

Người lữ hành bắt đầu từ ô ở góc trên bên trái và cần đến ô ở góc dưới bên phải của bản đồ. Tại mỗi bước, người đó có thể di chuyển sang một trong bốn ô kề cạnh: trên, dưới, trái hoặc phải.

Do địa hình gồ ghề, những đoạn đường có độ cao thay đổi đột ngột sẽ rất khó vượt qua. Vì vậy, người lữ hành muốn tìm một con đường tránh được những đoạn dốc quá lớn.

Hãy giúp người lữ hành tìm một con đường sao cho độ chênh lệch độ cao lớn nhất giữa hai ô liên tiếp trên đường đi là nhỏ nhất có thể.

Đầu vào

Dòng đầu tiên chứa số nguyên ~N~ ~(2 \le N \le 500)~ là kích thước của bản đồ.

~N~ dòng tiếp theo, dòng thứ ~i~ chứa ~N~ số nguyên ~A[i][1], A[i][2], \ldots, A[i][N]~, trong đó ~A[i][j]~ là độ cao của ô ở hàng ~i~, cột ~j~ ~(1 \le A[i][j] \le 10^6)~.

Đầu ra

In ra một số nguyên duy nhất là độ chênh lệch độ cao lớn nhất giữa hai ô liên tiếp trên con đường tối ưu.

Subtask

Ví dụ

Đầu vào

4
3 5 7 7
2 4 4 7
3 3 5 4
9 5 8 5

Đầu ra

1

Giải thích