掉线城与虚弱勇士
说明
去年的12月1日的ACM校赛后，小明玩的《轩辕剑天之痕》已经被他通关了。他顺便也学习了游戏编程中很重要的搜索算法，毕竟很多公司笔试和面试都会考察。
现在大二的小明很喜欢玩一种网络游戏——《掉线城与虚弱勇士》
在这个游戏的迷宫中，你必须争分夺秒的从迷宫的入口走到出口，否则就会遇到掉线这种超级大BOSS把你一刀秒杀。在这种掉线的环境中，每走一步路需要花费一分钟的时间。
需要注意的是，迷宫中会有一些守卫，这些守卫很弱小，但是他们会拖延你一分钟的时间，使你更加接近掉线。
你要做的是在最短的时间中冲出这个迷宫，计算出这个最短的时间。
PS：守卫不一定要打，想办法在最短时间内冲出迷宫才是第一任务。
输入格式
第一行是一个整数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.”
1
7 8
#.#####.
#.a#..r.
#..#x...
..#..#.#
#...##..
.#......
........13