항구를 빠르게 탈출하기

클리어비어드 선장은 배를 점검하고 수리하기 위해 며칠 동안 항구에 머물렀다. 며칠이 지난 지금, 해적들은 뱃멀미가 아닌 '땅멀미'에 시달리기 시작했다. 선원 전체가 노를 저을 수 없을 만큼 아파지기 전에, 클리어비어드 선장은 최대한 빨리 항구를 빠져나가려 한다.

안타깝게도 항구에서 넓은 바다로 이어지는 길은 직선이 아니다. 사악한 해적들로부터 도시를 지키기 위해, 항구 입구는 도개교(drawbridge)로 가득 찬 미로처럼 되어 있다. 다리를 여는 데에는 시간이 걸리므로, 돌아가는 편이 오히려 더 빠를 수도 있다. 선장이 넓은 바다로 나가는 가장 빠른 길을 찾도록 도와주자.

지도는 격자로 주어진다. 해적들은 한 칸을 지나는 데 1분이 걸리는 속도로 노를 젓고, 배는 가로 또는 세로로만(대각선 이동은 불가능) 움직일 수 있다. 90도 방향 전환에는 추가 시간이 들지 않는다.

• 인접한 물 칸으로 이동하는 데에는 1분이 걸린다.
• 도개교 칸으로 이동하는 데에는 $1 + d$분이 걸린다 (노를 젓는 1분과 다리를 여는 $d$분).
• 넓은 바다는 지도에 그려져 있지 않으며, 지도 경계 바로 바깥에 있다. 경계에 있는 칸에서 지도 밖으로 노를 저어 나가는 데에도 1분이 걸린다.

참고: 해적은 배의 흔들림을 충분히 느끼지 못하면 땅멀미를 앓는다. 그래서 해적들은 럼주를 마시며 그 흔들림을 흉내 내곤 한다.

첫째 줄에는 테스트 케이스의 개수를 나타내는 정수 하나가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 한 줄에 세 정수 $h$, $w$ ($3 \le h, w \le 500$), $d$ ($0 \le d \le 50$)가 주어진다. 각각 지도의 높이와 너비, 그리고 다리를 여는 데 걸리는 지연 시간이다.
• 이어서 $w$개의 문자로 이루어진 $h$개의 줄이 주어지며, 지도를 나타낸다. 사용되는 문자는 다음과 같다.
  • S — 배의 시작 위치.
  • . — 물.
  • # — 땅.
  • @ — 도개교.

각 항구는 입구 하나를 제외하고는 완전히 땅으로 둘러싸여 있다.

각 테스트 케이스마다, 넓은 바다로 나가는 가장 빠른 경로의 이동 시간을 정수 하나로 한 줄에 출력한다. 넓은 바다로 나가는 경로는 항상 존재한다. 넓은 바다는 지도에 표시되지 않으므로, 배는 지도 경계 밖으로 나가야 넓은 바다에 도달할 수 있음에 유의하라.