#include<bits/stdc++.h>
using namespace std;
int N, sx, sy, ex, ey;
const int MAXN = 4030303;
char arr[1010][1010];
int st;
vector<pair<int, int> > conn[MAXN];
bool visit[MAXN];
int tp;
int dijk()
{
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > Q;
Q.emplace(0, sx*N+sy);
while(!Q.empty())
{
int dist, no; tie(dist, no) = Q.top(); Q.pop();
//printf("%d\n", no);
if(no==ex*N+ey) return dist;
if(visit[no]) continue;
visit[no] = true;
for(auto x: conn[no])
{
int targ, w;
tie(targ, w) = x;
Q.emplace(w+dist, targ);
}
}
return -1;
}
int main()
{
scanf("%d", &N); tp = N*N+N+1;
for(int i=1; i<=N; ++i)
scanf("%s", arr[i]+1);
for(int i=1; i<=N; ++i)
for(int j=1; j<=N; ++j)
{
if(arr[i][j] == 'M')
{
tie(sx, sy) = tie(i, j);
arr[i][j] = '.';
}
if(arr[i][j] == 'H')
{
tie(ex, ey) = tie(i, j);
arr[i][j] = '.';
}
}
for(int i=1; i<=N; ++i)
{
int cnt = -1;
vector<int> inserted;
vector<int> weight;
for(int j=0; j<=N+1; ++j)
{
if(arr[i][j] == '.')
{
if(arr[i][j-1] != '.')
{
weight.push_back(cnt);
inserted.push_back(tp);
}
conn[tp].emplace_back(i*N+j, 0);
conn[i*N+j].emplace_back(tp+1, 0);
}
else
{
if(j!=0 && arr[i][j-1] == '.')
cnt = 0, tp += 2;
++cnt;
}
}
for(int i=0; i<(int)inserted.size()-1; ++i)
{
int ptp = inserted[i], ntp = inserted[i+1], w = weight[i+1]*weight[i+1];
conn[ptp+1].emplace_back(ntp, w);
conn[ntp+1].emplace_back(ptp, w);
}
}
for(int j=1; j<=N; ++j)
{
int cnt = -1;
vector<int> inserted, weight;
for(int i=0; i<=N+1; ++i)
{
if(arr[i][j] == '.')
{
if(arr[i-1][j] != '.')
{
weight.push_back(cnt);
inserted.push_back(tp);
}
conn[tp].emplace_back(i*N+j, 0);
conn[i*N+j].emplace_back(tp+1, 0);
}
else
{
if(i!=0 && arr[i-1][j] == '.')
cnt=0, tp += 2;
++cnt;
}
}
for(int i=0; i<(int)inserted.size()-1; ++i)
{
int ptp = inserted[i], ntp = inserted[i+1], w = weight[i+1]*weight[i+1];
conn[ptp+1].emplace_back(ntp, w);
conn[ntp+1].emplace_back(ptp, w);
}
}
printf("%d\n", dijk());
}
