Background

Special for beginners, ^_^

Description

约翰和牛贝茜享受了最有趣的假期，他们花了一整天在山上漫步，最后疲惫地回到他们假日的小屋。

由于爬山需要很多体力，而且他们已经非常疲惫，所以他们想要穿过一条最高点和最低点高差最小的路径回到他们的小屋，尽管这个样的路径或许很长，帮助约翰找到这样一条易于攀登的路线！

整座山的地图用一个N×N(2<N<100)的方阵给出，方阵中填充了一些描述海拔的整数(0<任意高<110)，约翰和贝茜现在在地图的左上角（第一行，第一列）而小木屋在地图的右下角（第N行，第N列），他们可以向上走，向下走，向右走，向左走，但是不能穿越对角线。

Format

Input

第1行输入一个单独的整数N接下来输入NxN的矩阵.

Output

一个整数，表示路径上最高点和最低点的高度差。

Samples

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

2

Limitation

1s, 1024KiB for each test case.