Nông dân John và chú bò Bessie của anh đã bắt đầu kỳ nghỉ hè lý thú của mình. Họ dành cả ngày để đi bộ trên những ngọn núi, và sau đó trở về cabin nghỉ dưỡng vào cuối ngày.

Bản đồ bao gồm các ngọn núi được cho bởi ma trận \(N\times N\) (\(2\leq N\leq100\)) ô mang giá trị là độ cao của ô đó (\(0\leq\) độ cao \(\leq110\)). Bác John và Bessie hiện đang ở ô góc trên bên trái (hàng \(1\), cột \(1\)) và cabin ở ô góc dưới bên phải (hàng \(N\), cột \(N\)). Họ có thể di chuyển sang phải, sang trái, lên trên hoặc xuống dưới nhưng không thể đi theo đường chéo (nghĩa là di chuyển theo các ô chung cạnh).

Vì việc leo núi đòi hỏi rất nhiều năng lượng và họ đã rất mệt mỏi, John muốn trở lại cabin bằng cách sử dụng con đường có độ chênh lệch giữa độ cao thấp nhất và cao nhất là nhỏ nhất, không quan trọng con đường đó dài bao nhiêu. Hãy giúp bác John và chú bò Bessie tìm ra con đường đó nhé!

Input

• Dòng đầu chứa một số nguyên dương \(N\);
• Dòng \(2\ldots N+1\): Mỗi dòng chứa \(N\) số nguyên dương, thể hiện độ cao của ô vuông tương ứng.

Output

• In ra một số nguyên dương duy nhất là độ chênh lệch nhỏ nhất.

Ví dụ

Sample input

5
1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 3 4
4 3 0 2 1

Sample output

2

Nguồn bài: USACO 2003 US Open.