감염된 땅

치명적인 바이러스가 발생했지만, 신속한 방역 조치 덕분에 감염은 정사각형 격자 형태의 구역들 안에 갇혔습니다. 시간이 지남에 따라 감염 구역은 정해진 규칙에 따라 변합니다. 매 시간 단계마다 모든 구역은 자신과 직접 인접한 여덟 개 구역(가로, 세로, 대각선)의 상태를 보고 다음 규칙으로 감염 상태를 갱신합니다.

• 감염된 구역은 인접한 감염 구역이 둘 또는 셋이면 계속 감염 상태로 남습니다.
• 감염되지 않은 구역은 인접한 감염 구역이 정확히 셋이면 감염됩니다.
• 그 밖의 경우 구역은 바이러스가 사라진 상태가 됩니다.

당신은 시제품 방역 차량을 지휘하여 모든 구역을 소독해야 합니다. 차량은 다음과 같이 동작합니다.

• 매 시간 단계가 시작될 때 차량을 인접한 여덟 구역 중 하나로 이동시킵니다. 차량은 감염된 구역으로 이동할 수 없고, 격자 밖으로 나갈 수 없으며, 제자리에 머무를 수도 없습니다.
• 차량이 이동한 뒤에는 차량이 새로 위치한 구역을 제외한 모든 구역이 위 규칙에 따라 감염 상태를 동시에 갱신합니다.
• 차량이 어떤 구역에 있는 동안 그 구역은 보호되어, 인접한 감염 구역이 정확히 셋이더라도 감염되지 않습니다. 이 보호 효과는 차량이 떠나는 순간 사라지며, 그 뒤에는 다른 구역과 마찬가지로 감염될 수 있습니다.
• 규칙을 적용해 인접 감염 수를 셀 때, 차량이 현재 위치한 구역은 그 자신은 감염되지 않았더라도 인접한 구역들에게는 감염 구역으로 계산됩니다.

예를 들어 $5 \times 5$ 격자에서는 차량이 남서쪽, 그다음 서쪽, 그다음 동쪽으로 이동하는 세 시간 단계만에 전체를 소독할 수 있습니다. 이런 과정에서, 감염되지 않았던 구역이 인접한 감염 구역 둘에 차량의 구역까지 더해 감염 구역이 셋이 되어 감염될 수 있고, 반대로 차량이 위치한 구역은 인접한 감염 구역이 셋이어도 감염되지 않습니다.

모든 구역을 소독하는 가장 짧은 차량 이동 명령 열의 길이를 구하세요.

입력은 여러 데이터셋으로 이루어지며, 0 하나만 있는 줄로 끝납니다.

각 데이터셋의 형식은 다음과 같습니다.

n
r1
r2
...
rn

여기서 $n$ ($1 \le n \le 5$)은 격자의 한 변 길이이며, 격자는 $n \times n$개의 구역으로 이루어집니다. 이어지는 $n$개의 줄은 각각 초기 상태를 나타내는 정확히 $n$개의 문자로 된 문자열이고, 각 문자는 다음 중 하나입니다.

• #: 감염된 구역
• .: 바이러스가 없는 구역
• @: 차량의 초기 위치

@가 있는 구역은 정확히 하나이며, 등장하는 문자는 #, ., @뿐입니다.

각 데이터셋에 대해 모든 구역을 소독하는 데 필요한 최소 시간 단계 수를 한 줄에 하나씩 출력하세요. 어떤 이동 명령 열로도 완전한 소독이 불가능하면 -1을 출력합니다. 그 밖의 어떤 문자도 출력하지 마세요.