#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=4e4+5,inf=1e9;
int t,n,m,id[N],tot3,ans;
int dfn[N],low[N],tot1,tot2,stak[N],top2;
int tot4,dep[N],par[N],seg[N],siz[N],top[N],son[N];
int dis[5][105][105];
vector<int>v[N],g[N];
char s[105][105];
void tarjan(int x){
	dfn[x]=low[x]=++tot1;
	stak[++top2]=x;
	for(int i=0;i<v[x].size();i++){
		if(!dfn[v[x][i]]){
			tarjan(v[x][i]);
			low[x]=min(low[x],low[v[x][i]]);
			if(dfn[x]<=low[v[x][i]]){
				tot2++;
				while(stak[top2]!=v[x][i]){
					g[tot2].push_back(stak[top2]);
					g[stak[top2]].push_back(tot2);
					top2--;
				}
				g[tot2].push_back(v[x][i]);
				g[v[x][i]].push_back(tot2);
				g[tot2].push_back(x);
				g[x].push_back(tot2);
				top2--;
			}
		}
		else low[x]=min(low[x],dfn[v[x][i]]);
	}
}
void dfs1(int x,int fa){
	siz[x]=1;dep[x]=dep[fa]+1;par[x]=fa;
	for(int i=0;i<g[x].size();i++)
		if(g[x][i]!=fa){
			dfs1(g[x][i],x);
			siz[x]+=siz[g[x][i]];
			if(siz[g[x][i]]>siz[son[x]]) son[x]=g[x][i];
		}
}
void dfs2(int x,int topf){
	top[x]=topf;seg[x]=++tot4;
	if(son[x]) dfs2(son[x],topf);
	for(int i=0;i<g[x].size();i++)
		if(!top[g[x][i]])
			dfs2(g[x][i],g[x][i]);
}
int yyz(int x,int y){return (x-1)*m+y;}
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
bool check(int x,int y){return (x>=1)&&(y>=1)&&(x<=n)&&(y<=m)&&(s[x][y]!='S');}
int get(int x,int y){return id[yyz(x,y)];}
bool ask(int x,int y,int z){
	if(x==z) return 0;
	if(y==z) return 0;
	if(par[x])if(par[y])if(par[x]==par[y]) return 1;
	if(par[par[x]]==y) return 1;
	if(par[par[y]]==x) return 1;
	z=seg[z];
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		if(seg[top[x]]<=z&&z<=seg[x]) return 0;
		x=par[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	if(seg[x]<=z&&z<=seg[y]) return 0;
	return 1;
}
struct node{int x,y,z;};
queue<node>q;
void qwq(int x,int y,int z){
	for(int i=0;i<4;i++){
		if(s[x+dx[i]][y+dy[i]]=='S') continue;
		if(s[x-dx[i]][y-dy[i]]=='S') continue;
		if(ask(get(x+dx[z],y+dy[z]),get(x+dx[i],y+dy[i]),get(x,y)))
			if(dis[i][x-dx[i]][y-dy[i]]==inf){
				dis[i][x-dx[i]][y-dy[i]]=dis[z][x][y]+1;
				q.push(node{x-dx[i],y-dy[i],i});
			}
	}
}
void work(){
	int px,py,p1,p2;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(s[i][j]=='P'){
				px=i,py=j;
				break;
			}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(s[i][j]=='M'){
				p1=i,p2=j;
				break;
			}
	for(int i=0,nx,ny;i<4;i++){
		nx=px+dx[i],ny=py+dy[i];
		if(s[nx][ny]=='S') continue;
		if(ask(get(p1,p2),get(nx,ny),get(px,py))){
			dis[i][px][py]=0;
			q.push(node{px,py,i});
		}
	}
	while(!q.empty()){
		node u=q.front();
		q.pop();
		qwq(u.x,u.y,u.z);
	}
}
int main(){
//	freopen("A.in","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
		tot3=tot4=tot1=tot2=top2=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(s[i][j]!='S')
					id[yyz(i,j)]=++tot3;
		tot2=tot3;
		for(int i=1,nx,ny;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(s[i][j]!='S')
					for(int op=0;op<4;op++){
						nx=i+dx[op],ny=j+dy[op];
						if(check(nx,ny))
							v[get(i,j)].push_back(get(nx,ny));
					}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(s[i][j]!='S')
					if(!dfn[get(i,j)]){
						tarjan(get(i,j));
						top2=0;
					}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(s[i][j]!='S')
					if(!dep[get(i,j)])
						dfs1(get(i,j),0);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(s[i][j]!='S')
					if(!seg[get(i,j)])
						dfs2(get(i,j),get(i,j));
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				for(int op=0;op<4;op++)
					dis[op][i][j]=inf;
		work();
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(s[i][j]=='K'){
					ans=inf;
					for(int op=0;op<4;op++) ans=min(ans,dis[op][i][j]);
					if(ans==inf) puts("NO");
					else printf("%d\n",ans);
				}
		for(int i=1;i<=tot2;i++){
			v[i].clear(),g[i].clear();
			dfn[i]=low[i]=0;
			par[i]=seg[i]=dep[i]=siz[i]=top[i]=son[i]=0;
		}
	}
	return 0;
}

WA，但是讨论区的数据过了