/*
██████████ ███████ ██
░░░░░██░░░ ░██░░░░██ ░██
░██ ░██ ░██ ██████ ███████ ░██
░██ ░██ ░██ ░░░░░░██ ░░██░░░██░██████
░██ ░██ ░██ ███████ ░██ ░██░██░░░██
░██ ░██ ██ ██░░░░██ ░██ ░██░██ ░██
░██ █████ ░███████ ░░████████ ███ ░██░██ ░██
░░ ░░░░░ ░░░░░░░ ░░░░░░░░ ░░░ ░░ ░░ ░░
*/
#include <bits/stdc++.h>
#define input ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl '\n'
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define ce cout << endl
#define FOR(i, l, r) for (int i = l; i <= r; i++)
#define FOR2(i, l, r) for (int i = l; i >= r; i--)
using namespace std;
using ll = long long;
using str = string;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
const ll N = 1e5+1;
const ll LOGN = 19;
const int INF = numeric_limits<int>::max();
const ll MOD = 998244353;
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
char op[] = {'D','U','R','L'};
void solve() {
int n , s;
cin >> n >> s;
vector<vector<char>> matrix(n,vector<char>(n));
vector<pii> hives;
pii mecho;
pii end;
FOR(i,0,n-1){
FOR(j,0,n-1)
{
cin >> matrix[i][j];
if(matrix[i][j] == 'H') hives.pb({i,j});
else if(matrix[i][j] == 'M') mecho ={i,j};
else if(matrix[i][j] == 'D') end = {i,j};
}
}
function<bool(int,int)> inside =[&] (int i ,int j){
return (i > - 1 && i < n && j > -1 && j < n && matrix[i][j] != 'T' && matrix[i][j] != 'H' );
};
vector<vector<int>> dist (n,vector<int> (n,INF));
deque<pii> q;
for(auto i : hives){
q.pb(i);
dist[i.fi][i.se] = 0;
}
while(q.size()){
pii c = q.front();
q.pop_front();
for(int i = 0 ; i < n ; i ++){
int di = c.fi + dx[i] , dj = c.se + dy[i];
if(inside(di,dj) && dist[di][dj] == INF){
if(matrix[di][dj] == 'D') continue;
dist[di][dj] = dist[c.fi][c.se] + 1;
q.pb({di,dj});
}
}
}
int l = -1 ;
int h = dist[mecho.fi][mecho.se] + 1;
while( l < h){
int m = l + h + 1 >> 1;
deque<pair<pii,pii>> mq;
vector<vector<int>> dist_m(n,vector<int>(n,INF));
mq.pb({mecho,{0,s}});
dist_m[mecho.fi][mecho.se] = 0;
while(mq.size()){
const auto &[c_pos,move] = mq.front();
mq.pop_front();
if(move.se == 0 && dist[c_pos.fi][c_pos.se] <= move.fi + 1) continue;
for(int i = 0 ; i < 4 ; i ++){
int di = c_pos.fi + dx[i] , dj = c_pos.se + dy[i];
if(inside(di,dj) && dist_m[di][dj] == INF ){
if(move.se == 0 && dist[di][dj] > dist_m[c_pos.fi][c_pos.se] + 1 + m ){
dist_m[di][dj] = move.fi + 1;
mq.pb({{di,dj},{move.fi + 1,s - 1}});
}
else if(move.se > 0 && dist[di][dj] > dist_m[c_pos.fi][c_pos.se] + m){
dist_m[di][dj] = move.fi;
mq.pb({{di,dj},{move.fi ,move.se - 1}});
}
}
}
}
if(dist_m[end.fi][end.se] != INF) l = m;
else h = m - 1;
}
cout << l <<endl;
}
int main() {
input
const bool cap = true;
if (cap)
solve();
else {
ll t;
cin >> t;
while (t--) solve();
}
}
