//This code is written by sarthakgangwal
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define tc int t;cin>>t;while(t--)
#define el "/n"
#define sp ' '
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define ll long long int
#define ld long double
#define vll vector<long long int>
#define vvll vector<vector<long long int>>
#define vvpll vector<vector<pair<long long int, long long int>>>
#define vpll vector<pair<long long int,long long int>>
#define vb vector<bool>
#define pb push_back
#define pll pair<long long int,long long int>
#define ff first
#define ss second
#define I(x) ll x;cin>>x
#define CC(x) cout << (x) << endl
#define mod 1000000007
#define PI 3.14159265
long long INF = 2e18;
#define vll_in(v,n) for(ll i=0;i<=n-1;i++){ ll x;cin>>x; v.push_back(x);}
#define vvll_in(mat,r,c) for(ll i=0;i<=r-1;i++){ vector<ll> v;for(ll j=0;j<=c-1;j++){ll x;cin>>x;v.push_back(x);};mat.push_back(v);}
void print(bool k){cout << (k ? "YES" : "NO") <<"\n";}
void print(vll k,string sep = " ",string endline = "\n") {for (ll &i : k) cout << i << sep; cout << endline;}
#define all(x) (x).begin(), (x).end()
/*-------------------------------------Imp Concepts---------------------------------------------->
48-57 -> 0-9
65-90 -> A-Z
97-122 -> a-z
(a +-* b) mod M = ((a mod M) +-* (b mod M)) mod M.
use ordered set using oset<ll> , 2 extra functions
.order_of_key(k) gives number of items strictly smaller than k
.find_by_order(k) gives iterator to kth element in set 0 indexing
rest all functionalities are same as stl set like lowerbound upperbound erase find etc
use ordered multiset using oset<pll>
search upper_bound({val,-1})
insert insert({val,index}) index used so same val can be inserted uniquely
delete .erase( .upper_bound({val,-1}))
-----------------------------CODE BEGIN :)-----------------------------------------*/
ll forest[802][802];
vector<vector<pll>> M_ini(802,vpll(802,{INF,INF}));
vector<vector<pll>> M;
ll mx,my;
ll dx,dy;
vpll bees;
ll n,s;
ll movy[4] = {-1,0,1,0};
ll movx[4] = {0,1,0,-1};
bool ok=0;
void bfs1(){
queue<pll> q;
for(pll p:bees){q.push(p);}
while(!q.empty()){
pll top = q.front();q.pop();
ll x =top.ff, y=top.ss;
for(int i=0;i<4;i++){
ll xx=x+movx[i],yy=y+movy[i];
if(forest[xx][yy]==-1){
forest[xx][yy]=1+forest[x][y];
q.push({xx,yy});
}
}
}
return;
}
bool bfs2(ll st){
M=M_ini;
if(forest[mx][my]<=st){return 0;}
queue<pll> q;
q.push({mx,my});
M[mx][my]={st,0};
while(!q.empty()){
pll top = q.front();q.pop();
ll x =top.ff, y=top.ss;
ll tim=M[x][y].ff, stp=M[x][y].ss;
for(int i=0;i<4;i++){
ll xx=x+movx[i],yy=y+movy[i];
if(xx==dx && yy==dy){ok=1;return 1;}
if(M[xx][yy].ff==INF && forest[xx][yy]!=-2){
if(stp<s-1){M[xx][yy]={tim,stp+1};}
else{M[xx][yy]={tim+1,0};}
if(M[xx][yy].ff<=forest[xx][yy]){
q.push({xx,yy});
}
else{
M[xx][yy].ff=INF;M[xx][yy].ss=INF;
}
}
}
}
return 0;
}
int main(){
fast
{
cin>>n>>s;
char x;
for(ll i=0;i<802;i++){
forest[0][i]=-2;
forest[n+1][i]=-2;
forest[801][i]=-2;
forest[i][0]=-2;
forest[i][n+1]=-2;
forest[i][801]=-2;
}
for(ll i=1;i<=n;i++){
for(ll j=1;j<=n;j++){
cin>>x;
if(x=='M'){mx=i;my=j;forest[i][j]=-1;}
if(x=='G'){forest[i][j]=-1;}
if(x=='H'){forest[i][j]=0;bees.pb({i,j});}
if(x=='T'){forest[i][j]=-2;}
if(x=='D'){forest[i][j]=-1;dx=i;dy=j;}
}
}
bfs1();
ll l=0,h=forest[dx][dy]+1;
while(l<h){
ll m = (l+h)/2;
if(m==l){if(bfs2(h)){l=h;}break;}
if(bfs2(m)){l=m;}
else{h=m-1;}
}
if(!ok){CC(-1);}
else{CC(l);}
}
}
