불

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀 있다. 건물 곳곳에 불이 났고, 상근이는 탈출을 시도한다.

매초 불은 현재 불이 붙은 각 칸에서 상하좌우로 인접한 빈 공간으로 번진다. 벽에는 불이 옮겨붙지 않는다. 상근이는 매초 상하좌우로 인접한 칸 하나로 이동할 수 있다. 벽을 통과할 수 없고, 이미 불이 번진 칸이나 바로 그 순간에 불이 옮겨붙는 칸으로는 이동할 수 없다. 다만, 자신이 있는 칸에 불이 옮겨붙는 것과 동시에 다른 칸으로 이동하는 것은 가능하다.

상근이가 지도의 경계 바깥으로 나가는 순간 탈출에 성공한 것으로 본다. 건물의 지도가 주어졌을 때, 상근이가 탈출하는 데 걸리는 가장 빠른 시간을 구하여라.

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개이다.

각 테스트 케이스의 첫째 줄에는 지도의 너비 $w$와 높이 $h$가 주어진다. ($1 \le w, h \le 1000$)

다음 $h$개의 줄에는 각각 $w$개의 문자로 이루어진 지도가 주어진다. 각 문자의 의미는 다음과 같다.

• . : 빈 공간
• # : 벽
• @ : 상근이의 시작 위치
• * : 불

각 지도에서 @는 정확히 한 개이다.

각 테스트 케이스마다 상근이가 건물을 탈출하는 가장 빠른 시간을 한 줄에 하나씩 출력한다. 탈출할 수 없는 경우에는 IMPOSSIBLE을 출력한다.