양 먹어치우기

양을 세는 프로그램은 잠드는 데 아무 도움이 되지 않았다. 그래서 새 게임 Sheep Frenzy를 만들었다. 플레이어는 울그르를 조종해 각 판에 있는 양을 모두 잡아먹고, 걸리는 시간을 최소로 줄이는 것이 목표다.

판은 $H \times W$ 격자이고, 각 칸은 다음 네 가지 중 하나다.

• U: 울그르가 출발하는 칸이다. 판마다 정확히 하나 있다.
• #: 양이 있는 칸이다. 양은 움직이지 않는다.
• .: 풀밭이다.
• X: 산이다. 울그르는 이 칸에 들어갈 수 없다.

울그르는 1초에 한 번 행동한다. 한 번의 행동은 상하좌우로 인접한 칸에 한 칸 이동하거나, 지금 서 있는 칸의 양을 먹는 것이다. 양은 그 양과 같은 칸에 서 있을 때만 먹을 수 있다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 판의 높이 $H$와 너비 $W$가 주어진다. 이어지는 $H$개의 줄에는 각각 $W$개의 문자가 주어져 판의 상태를 나타낸다.

• $0 < T \le 100$
• $0 < H, W \le 50$
• 한 테스트 케이스에 양은 1마리 이상 16마리 이하다.
• 각 테스트 케이스에 U는 정확히 하나 있다.
• 산은 모두 X로 표시하며, 울그르와 양은 산 위에 있지 않다.

각 테스트 케이스마다 울그르가 그 판의 양을 모두 먹는 데 걸리는 최소 시간을 초 단위로 한 줄에 출력한다. 모든 양을 먹을 수 없으면 대신 impossible을 출력한다.