城镇通常被划分为不同的区域，例如工业区、商业区和住宅区。如果某个住宅区距离所有商业区都很远，那么住在那里的居民每次购物都需要长途跋涉，这是不理想的。

输入为一个 $n \times n$ 的方形区域网格。每个区域被标记为 1（住宅区）、2（工业区）或 3（商业区）。在区域间移动时，你可以向北、东、南或西移动，移动距离为你穿过的区域边界数量。因此，两个相邻区域之间的距离为 1，从位于 $(1, 1)$ 的区域（最西南角的区域）到位于 $(2, 3)$ 的区域的距离为 3（向东走一步，向北走两步）。你不能离开网格范围。

你的任务是找到从某个住宅区出发，到达距离该住宅区最近的商业区所需的最长距离。

输入格式

第一行包含一个整数 $n$（$2 \le n \le 1500$），随后有 $n$ 行，每行长度为 $n$，给出了城市区域的地图，表示为一个 $n \times n$ 的矩阵，其中每个元素根据区域类型为 1、2 或 3。你可以假设城市中包含所有三种类型的区域。

输出格式

输出一个整数 $d$，表示从住宅区到其最近商业区的最大距离。

样例

输入 1

4
1223
2123
2213
3212

输出 1

3

输入 2

2
12
33

输出 2

1