탈출

큰 정사각형 타일이 깔린 직사각형 방에 갇혔다. 지나갈 수 있는 타일도 있고, 장애물이나 벽으로 막힌 타일도 있다. 한 걸음에 가로나 세로로 맞닿은 타일 하나로 움직인다. 대각선으로는 움직이지 못한다.

뒤쫓는 사람을 따돌리려면 직선으로 움직여서는 안 된다. 그래서 꺾을 기회가 생길 때마다 꺾고, 한 방향으로 꼭 필요한 만큼보다 길게 가지 않는다. 예를 들어 남쪽에서 어떤 타일로 들어왔다면 왼쪽이나 오른쪽으로 꺾어 서쪽이나 동쪽으로 빠져나간다. 양옆이 모두 막혔을 때만 앞으로 곧장 나아간다. 왔던 길로 되돌아가는 일은 절대 없다.

출발할 때는 들어온 방향이 없다. 그래서 시작 타일에서는 지나갈 수 있는 이웃 타일이라면 어느 쪽으로든 첫 걸음을 뗄 수 있다.

방의 가장자리, 즉 첫 번째 행이나 마지막 행, 첫 번째 열이나 마지막 열에 놓인 타일을 밟는 순간 탈출한다. 방의 지도와 시작 위치가 주어질 때 탈출까지 몇 걸음이 걸리는지 구하라.

첫째 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 100$)가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

• 한 줄에 방의 높이와 너비를 뜻하는 두 정수 $h$와 $w$ ($1 \le h, w \le 80$)가 공백으로 구분되어 주어진다.
• 이어지는 $h$개 줄에 방의 모습이 한 줄마다 $w$개의 문자로 주어진다. 각 문자는 지나갈 수 있는 칸을 뜻하는 ., 막힌 칸을 뜻하는 #, 시작 위치를 뜻하는 @ 중 하나다. 방 하나에 @는 정확히 하나 있다.

각 테스트 케이스마다 방의 가장자리에 닿는 데 필요한 최소 걸음 수를 한 줄에 출력한다. 탈출할 방법이 없으면 -1을 출력한다.