용도 지역

도시는 보통 공업 지역, 상업 지역, 주거 지역 같은 용도 지역으로 나뉜다. 어떤 주거 지역이 모든 상업 지역에서 멀리 떨어져 있으면 그곳 주민은 장을 볼 때마다 먼 길을 오가야 하므로 좋지 않다.

도시는 $n \times n$ 격자로 주어진다. 각 칸은 주거 지역이면 1, 공업 지역이면 2, 상업 지역이면 3으로 표시한다. 한 칸에서 다른 칸으로 이동할 때는 북쪽, 동쪽, 남쪽, 서쪽으로만 움직이며, 이동 거리는 지나간 칸 경계의 개수다. 그래서 인접한 두 칸 사이의 거리는 1이고, 가장 남서쪽 칸인 $(1, 1)$에서 칸 $(2, 3)$까지의 거리는 3이다. 동쪽으로 한 번, 북쪽으로 두 번 움직이면 되기 때문이다. 격자 밖으로는 나갈 수 없다.

각 주거 지역마다 가장 가까운 상업 지역까지의 거리를 재고, 그 값 중 최댓값을 구하라.

첫째 줄에 정수 $n$이 주어진다($2 \le n \le 1500$). 다음 $n$개의 줄에는 길이가 $n$인 문자열이 한 줄씩 주어져 도시의 용도 지역 지도를 이룬다. 각 문자는 그 칸의 용도에 따라 1, 2, 3 중 하나다. 도시에는 세 종류의 지역이 모두 적어도 하나씩 있다.

주거 지역에서 가장 가까운 상업 지역까지의 거리 중 최댓값 $d$를 한 줄에 출력한다.