Description

传说阿童木轻松找到工作后，人变得更自信了，他觉得自己已经有了物质上的保证，可以为心爱的MM带来幸福，于是这个周末，阿童木买了99朵玫瑰花准备向MM表白，没想到心爱的女孩子被何大侠抓走了，为了救回MM，阿童木决心赴汤蹈火，在所不辞。历经一系列的战斗，阿童木终于到达了何大侠的营地，但此时的阿童木所剩下的能量已经不多了。和大侠的营地是一个N×N的矩阵，矩阵上的每个数字代表该据点的海拔，现在阿童木站在坐标（1，1）的位置，阿童木通过最新的卫星定位技术探测到心爱的MM在（N，N）的位置，但是阿童木每次只能在当前据点向上，下，左，右移动到相邻的据点，并且不能走对角线。由于阿童木所剩能量不多，到达MM所在的据点还要和何大侠决斗，所以阿童木决定选择一条最省能量的路线，留下尽可能多的能量打败何大侠。已知阿童木的能量消耗与路线上的最高据点与最低据点的差值有关，差值越大，消耗能量越多。
为了救出心爱的MM，阿童木必须与何大侠斗智斗勇，善良的参赛者，为了阿童木的幸福，请帮忙设计一条最省能量的路线吧。

Input

第一行给出矩阵的行数N。（2<=N<=100）
剩下N行给出据点的矩阵，矩阵的值代表据点的海拔H(0<=H<=110)。

Output

对于每组测试数据，输出最优路线上的最高据点和最低据点的差值。

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

HINT

Source