#include <bits/stdc++.h>
using
namespace
std;
const
int
N=5e2+66;
int
visit[N][N][2];
char
mp[N][N];
int
dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
struct
node{
int
x,y;
int
flag,step;
};
int
n,m;
int
dfs(int
x,int
y)
{
int
tx,ty;
memset(visit,0,sizeof(visit));
queue<node> que;
node tmp; tmp.x=x; tmp.y=y; tmp.flag=0; tmp.step=0;
visit[x][y][tmp.flag]=1; que.push(tmp);
while(!que.empty())
{
node q=que.front();
que.pop();
if(mp[q.x][q.y]== 'E')return
q.step;
for(int
i=0;i<4;i++)
{
tx=q.x+dir[i][0];
ty=q.y+dir[i][1];
if(tx>=0&&tx<n&&ty>=0&&ty<m&&mp[tx][ty]!='#')
{
node tp;
if(mp[tx][ty]=='K')
tp.flag=1;
else
tp.flag=q.flag;
if(visit[tx][ty][tp.flag])continue;
visit[tx][ty][tp.flag]=1;
if(mp[tx][ty]== 'E'&&!visit[tx][ty][1])
continue;
tp.x=tx;
tp.y=ty;
tp.step=q.step + 1;
que.push(tp);
}
}
}
return
-1;
}
int
main()
{
int
t;
int
i,j;
cin>>t;
while(t--)
{
int
tx,ty,ans;
cin>>n>>m;
getchar();
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
scanf("%c",&mp[i][j]);
if(mp[i][j]=='P')
{
tx=i; ty=j;
}
if(i!=n-1&&j==m-1)getchar();
}
ans=dfs(tx,ty);
if(ans==-1)
printf("No solution\n");
else
printf("%d\n",ans);
}
return
0;
}