#include<iostream>
#include<queue>
using namespace std;
const int maxn = 500 + 5;
char map[maxn][maxn];
int dirx[4] = {1, 0, 0,
-1};
int diry[4] = {0, 1, -1, 0};
int n, m, d;
int ex, ey;
struct point{
int x;
int y;
int v;
const bool operator <
(const struct point a)const{ //重载<号, v > a.v升序, v < a.v
降序
return v > a.v;
}
};
int bfs(int x, int y){
point q1,
q2;
priority_queue<point>Q;
q1.x = x;
q1.y = y;
q1.v =
1;
Q.push(q1);
while(!Q.empty()){
q2 =
Q.top();
Q.pop();
map[q2.x][q2.y] = 0;
if(q2.x == ex &&
q2.y == ey)
return q2.v;
for(int i=0; i<4; i++){
q1.x = q2.x
+ dirx[i];
q1.y = q2.y + diry[i];
if(map[q1.x][q1.y] ==
‘.‘)
q1.v = q2.v + 1;
else
q1.v = q2.v + d;
if(q1.x
>= 0 && q1.y >= 0 && q1.x < n && q1.y < m
&& map[q1.x][q1.y] && map[q1.x][q1.y] !=
‘#‘){
Q.push(q1);
map[q1.x][q1.y] =
0;
}
}
}
}
int main(){
int
t;
cin>>t;
while(t--){
cin>>n>>m>>d;
d++;
//等待时间和通过使用的时间
int sx, sy;
for(int i=0; i<n;
i++){
for(int j=0; j<m;
j++){
cin>>map[i][j];
if(map[i][j] == ‘S‘){
sx =
i;
sy = j;
}
if((i == 0 || j == 0 || i == n - 1 || j == n
- 1 ) && map[i][j] != ‘#‘){
ex = i;
ey =
j;
}
}
}
cout<<bfs(sx,
sy)<<endl;
}
return 0;
}