Untitled

///Dux
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define reset(a) memset(a, 0, sizeof(a))
#define For(i,a,b)    for(int i=a; i<=b; i++)
#define Fod(i,a,b)    for(int i=a; i>=b; i--)
#define vii vector<int, int>
#define vll vector<ll, ll>
#define NMAX 102
#define MOD (ll)(998244353)
#define oo 111000111
#define TIME cout << "\nTime: " << clock()/(double) 1000 << "s "
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL)
#define dux "SPELL"
#define inp freopen(dux".inp", "r", stdin);
#define out freopen(dux".out", "w", stdout);
#define MN int main()

using namespace std;

int n;
char a[NMAX][NMAX];
int d1[2][NMAX][NMAX], d2[2][NMAX][NMAX];
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
int dxx[] = {1, 1, -1, -1, -2, -2, 2, 2}, dyy[] = {-2, 2, -2, 2, 1, -1, 1, -1};

bool Inside(int u, int v)
{
    if(u >= 1 && v >= 1 && u <= n && v <= n && a[u][v] != '#')  return true;
    return false;
}

void bfs1()
{
    queue<pair<int, pair<int, int> > > q;
    memset(d1, 0x3f, sizeof d1);
    For(i, 1, n)    For(j, 1, n)    if(a[i][j] == 'T')  q.push({0, {i, j}}), d1[0][i][j] = 0;

    while(!q.empty())
    {
        int x = q.front().fi;
        int u = q.front().se.fi;
        int v = q.front().se.se;
        q.pop();
        x = 1 - x;
        For(k, 0, 7)
        {
            int newu = u + dx[k];
            int newv = v + dy[k];
//            cout << newu << " " << newv << endl;
            if(Inside(newu, newv) && d1[x][newu][newv] > d1[1-x][u][v] + 1)
            {

                d1[x][newu][newv] = d1[1-x][u][v] + 1;
                q.push({x,{newu, newv}});
            }
        }
    }
}

void bfs2(int dung, int ngoc)
{
    queue<pair<int, pair<int, int> > > q;
    memset(d2, 0x3f, sizeof d2);
    q.push({0, {dung, ngoc}});
    d2[0][dung][ngoc] = 0;

    while(!q.empty())
    {
        int x = q.front().fi;
        int u = q.front().se.fi;
        int v = q.front().se.se;
        q.pop();
        x = 1 - x;
        For(i, 0, 7)
        {
            int newu = u + dxx[i];
            int newv = v + dyy[i];
            if(Inside(newu, newv) && d2[x][newu][newv] > d2[1-x][u][v] + 1)
            {
                d2[x][newu][newv] = d2[1-x][u][v] + 1;
                q.push({x, {newu, newv}});
            }
        }
    }
    For(k, 0, 1)
    {
        For(i, 1, n)
        {
            For(j, 1, n)
            {
                d1[k][i][j] = max(d1[k][i][j], d2[k][i][j]);
            }
        }
    }
}

MN
{
    fast;
    cin >> n;
    For(i, 1, n)    For(j, 1, n)    cin >> a[i][j];
    bfs1();
    For(i, 1, n)    For(j, 1, n)    if(a[i][j] == 'M')  bfs2(i, j);
    int res = oo;
    For(i, 1, n)
    {
        For(j, 1, n)
        {
            res = min(res, d1[0][i][j]);
            res = min(res, d1[1][i][j]);
        }
    }
    if(res != oo)   cout << res;
    else cout << -1;
}