去年的12月1日的ACM校赛后，小明玩的《轩辕剑天之痕》已经被他通关了。他顺便也学习了游戏编程中很重要的搜索算法，毕竟很多公司笔试和面试都会考察。

现在大二的小明很喜欢玩一种网络游戏——《掉线城与虚弱勇士》

<span style="font-size:10.5pt;font-family:'宋体';">在这个游戏的迷宫中，你必须争分夺秒的从迷宫的入口走到出口，否则就会遇到掉线这种超级大<span>BOSS</span><span>把你一刀秒杀。在这种掉线的环境中，每走一步路需要花费一分钟的时间。</span></span><span style="font-size:10.5pt;font-family:'宋体';"></span> 

<span style="font-size:10.5pt;font-family:'宋体';">需要注意的是，迷宫中会有一些守卫，这些守卫很弱小，但是他们会拖延你一分钟的时间，使你更加接近掉线。</span><span style="font-size:10.5pt;font-family:'宋体';"></span> 

<span style="font-size:10.5pt;font-family:'宋体';">你要做的是在最短的时间中冲出这个迷宫，计算出这个最短的时间。</span><span style="font-size:10.5pt;font-family:'宋体';"></span> 

<span style="font-size:10.5pt;font-family:'宋体';">PS<span>：守卫不一定要打，想办法在最短时间内冲出迷宫才是第一任务。</span></span><span style="font-size:10.5pt;font-family:'宋体';"></span> 

 

第一行是一个整数T，表示测试数据的组数（1<T<5)

对每一组测试样例，第一行为N，M，表示一个N*M的矩阵，即迷宫本身。(N,M<=100)

对迷宫来说，字符"." 代表路, "a" 小明的角色起始的位置,  "r" 代表出口的位置， "x"代表守卫的位置。

对每组测试数据，输出一行数据，表示最短花费的时间。

如果小明根本走不出去迷宫，请输出“Poor XIAOMING has to stay in the prison all his life.”