Problem D
Zoning

A town is often divided into zones, e.g, industrial zones, commercial zones, and residential zones. If some residential zone is very far from all commercial zones, then the people living there will have a long journey whenever they want to do some shopping, and this is undesirable.

The input will consist of an $n\times n$ grid of square zones. Each zone is labeled 1 (residential), 2 (industrial), or 3 (commercial). When travelling from one zone to another you are allowed to move north, east, south or west, and the distance travelled is the number of zone boundaries you traverse. So the distance between two adjacent zones is $1$, and the distance from the zone in square $(1,1)$ (the most south-westerly zone) to the zone in square $(2,3)$ is $3$ (one step east and two steps north). You may never move off the grid.

Your task is to find the longest distance one has to travel from a residential zone to get to the commercial zone closest to that residential zone.

Input

The first line of input contains an integer $n$, $2\leq n\leq 1500$, followed by $n$ lines of length $n$ giving the map of the city zones as an $n\times n$ matrix where each entry is 1, 2, or 3 depending on zone type. You can assume that the city has zones of all three types.

Output

Output a single integer $d$, the largest distance from a residential zone to its closest commercial zone.

4
1223
2123
2213
3212

3

2
12
33

1