1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define mp make_pair
15 #define fi first
16 #define se second
17 #define lc(x) (x << 1)
18 #define rc(x) (x << 1 | 1)
19 #define lowbit(x) (x & (-x))
20 #define ll long long
21 int h, w, d;
22 int sx, sy;
23 char maz[510][510];
24 int dx[] = {0, 0, 1, -1};
25 int dy[]=  {-1, 1, 0, 0};
26 bool visit[510][510];
27 struct Node {
28     int x, y, ti;
29     Node(){}
30     Node(int _x, int _y, int _ti) {
31         x = _x, y = _y, ti = _ti;
32     }
33     bool operator<(const Node &x) const {
34         return ti > x.ti;
35     }
36 };
37 
38 bool check(int x, int y) {
39     if(x >= 1 && x <= h && y >= 1 && y <= w) return true;
40     return false;
41 }
42 
43 void bfs() {
44     int ans;
45     memset(visit, false, sizeof(visit));
46     priority_queue<Node> que;
47     que.push(Node(sx, sy, 1));
48     while(!que.empty()) {
49         Node now = que.top();
50         que.pop();
51         if(visit[now.x][now.y]) continue;
52         else visit[now.x][now.y] = true;
53         if((now.x == 1 || now.x == h) || (now.y == 1 || now.y == w)) {
54             ans = now.ti;
55             break;
56         }
57         for(int i = 0; i < 4; i++) {
58             int nx = now.x + dx[i], ny = now.y + dy[i];
59             if(!check(nx, ny) || maz[nx][ny] == '#' || visit[nx][ny]) continue;
60             if(maz[nx][ny] == '@') que.push(Node(nx, ny, now.ti + d + 1));
61             else que.push(Node(nx, ny, now.ti + 1));
62         }
63     }
64     cout << ans << endl;
65 }
66 
67 int main() {
68     int T;
69     scanf("%d", &T);
70     while(T--) {
71         scanf("%d%d%d", &h, &w, &d);
72         for(int i = 1; i <= h; i++) {
73             scanf("%s", &maz[i][1]);
74         }
75         for(int i = 1; i <= h; i++) {
76             for(int j = 1; j <= w; j++) {
77                 if(maz[i][j] == 'S') sx = i, sy = j;
78             }
79         }
80         bfs();
81     }
82     return 0;
83 }
84