Infected Land

A deadly virus has broken out, but rapid public-health measures have confined the infection to a square grid of areas. Over time, infected areas evolve according to a fixed rule. At each time step every area updates its infection state based on its eight directly adjacent areas (horizontal, vertical, and diagonal):

• An infected area stays infected if it has two or three infected neighbors.
• An uninfected area becomes infected if it has exactly three infected neighbors.
• Otherwise the area becomes free of the virus.

You command a prototype anti-virus vehicle and must disinfect every area. The vehicle behaves as follows:

• At the beginning of each time step you move the vehicle to one of its eight adjacent areas. The vehicle may not move onto an infected area, may not leave the grid, and may not stay in place.
• After the vehicle moves, every area except the one the vehicle now occupies updates its infection state using the rules above.
• While the vehicle occupies an area, that area is protected and stays uninfected even if it has exactly three infected neighbors. The protection ends the moment the vehicle leaves, after which the area may become infected like any other.
• For the transition rules, the area the vehicle currently occupies counts as an infected neighbor of its adjacent areas, even though the occupied area itself remains uninfected.

For example, on a $5 \times 5$ grid the vehicle can disinfect the whole grid in three time steps by moving southwest, then west, then east. During such a sequence a previously uninfected area can become infected because two infected neighbors plus the vehicle's area total three infected neighbors, while the vehicle's own area stays uninfected even when three of its neighbors are infected.

Compute the length of the shortest sequence of vehicle moves that disinfects every area.

The input is a sequence of datasets and ends with a line containing a single 0.

Each dataset has the following form:

n
r1
r2
...
rn

Here $n$ ($1 \le n \le 5$) is the side length of the grid, so the grid consists of $n \times n$ areas. Each of the following $n$ lines is a string of exactly $n$ characters describing the initial state, where every character is one of:

• # for an infected area,
• . for an area free of the virus,
• @ for the initial location of the vehicle.

Exactly one area contains @, and only the characters #, ., and @ appear.

For each dataset, print on its own line the minimum number of time steps needed to disinfect every area. If no sequence of moves can fully disinfect the grid, print -1. Print nothing else.