// #ifndef khos
// #pragma GCC optimize ("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #endif
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#ifdef khos
#include "t_debug.cpp"
#else
#define debug(...) 42
#endif
using namespace std;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using indexed_multiset = tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update>;
// #define int int64_t
#define vi vector
#define ss second
#define ff first
#define TESTCASES
#define all(x) (x).begin(), (x).end()
const int mod = 1e9+7;
const int MAXN=4e6;
const int inf=1e9;
vi<int> dx={-1, 0, 1, 0};
vi<int> dy={0, -1, 0, 1};
void solution() {
int n,s;
cin >> n >> s;
vi<string> a(n);
vi<vi<int>> dist(n, vi<int> (n, -1));
queue<pair<int,int>> q;
int sx, sy, ex, ey;
for(int i=0; i<n; i++){
cin >> a[i];
for(int j=0; j<n; j++){
if(a[i][j]=='H'){
dist[i][j]=0;
q.push({i, j});
}
if(a[i][j]=='M'){
sx=i,sy=j;
}
if(a[i][j]=='D'){
ex=i,ey=j;
}
}
}
auto isvalid = [&](int nx, int ny) -> bool {
if(nx<0 || ny<0)return 0;
if(nx>=n || ny>=n)return 0;
if(a[nx][ny]!='G' && a[nx][ny]!='M')return false;
return true;
};
while(!q.empty()){
int x=q.front().ff;
int y=q.front().ss;
q.pop();
for(int i=0; i<4; i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(isvalid(nx, ny) && dist[nx][ny]==-1){
dist[nx][ny]=dist[x][y]+1;
q.push({nx, ny});
}
}
}
int l=0,r=n*n;
while(l<=r){
int mid=(l+r)/2;
queue<pair<int,int>> q;
q.push({sx, sy});
vi<vi<bool>> mp(n, vi<bool> (n));
vi<vi<int>> mt(n, vi<int> (n));
mp[sx][sy]=1;
if(dist[sx][sy]<=mid)q.pop();
while(!q.empty()){
auto [x, y] = q.front();
q.pop();
// if(mid==3)debug(sp, tm, x, y);
for(int i=0; i<4; i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(isvalid(nx, ny) && mp[nx][ny])continue;
if(isvalid(nx, ny) && (dist[nx][ny]-mid>(mt[x][y]+1)/s || dist[nx][ny]==-1)){
mt[nx][ny]=mt[x][y]+1;
mp[nx][ny]=1;
q.push({nx, ny});
}
}
}
bool ok=0;
for(int i=0; i<4; i++){
int nx=ex+dx[i];
int ny=ey+dy[i];
if(isvalid(nx, ny) && dist[nx][ny]-mid>mt[nx][ny]/s && mp[nx][ny]){
ok=true;
}
}
if(ok)l=mid+1;
else r=mid-1;
}
cout << l-1;
}
int32_t main(){
clock_t tStart = clock();
// freopen("atlarge.in", "r", stdin);
// freopen("atlarge.out", "w", stdout);
#ifdef khos
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int q = 1;
#ifdef TESTCASES
// cin >> q;
#endif
while(q--) {
solution();
cout << '\n';
}
cerr<<fixed<<setprecision(3)<<"\nTime Taken: "<<(double)(clock()- tStart)/CLOCKS_PER_SEC<<endl;
}
