跳马

Time Limit: 1000MS

Memory Limit: 65535K

Description

Andfive是个三国杀高手,但是玩象棋就是菜鸟了,有一天他遇到了这样的一个问题。

在一个8*8矩阵中,有一个马要从一个位置跳到另一个位置。但是下象棋的人都知道,“马是走日,象走田”。并且马在跳的时候,会遇到“蹩马脚”的情况,一旦在跳向这个方向的时候马脚被蹩住,是不能想这个方向跳的。(马向要跳的那个方向和马同一条直线上马的前面有子就是马脚。如图红马可以跳到标记O的地方,但是由于红炮蹩住了马脚,所以不能跳到标记X的地方。

1

Andfive想知道从起始位置到达目标位置最少可以用多少步到达,采用最少步数的路径有多少条,面对Andfive的求助,想成为ACM大神的你快来帮帮他吧。


Input

第一行输入一个整数n(n<10000),代表n个8*8的矩阵,每个矩阵中“#”代表可以行走的位置,“*”代表障碍物,“S”代表起点,“T”代表终点。


Output

若不能到达终点“T”,输出“No way!”

如果可以到达,请输出最短路径大小和条数。

Sample Input

2
*###*###
####S###
##**####
#*##***#
########
#*#*##*#
#*######
T##*####

********
S######*
########
#####T##
########
********
#######*
########

Sample Output

No way!
3 4

Hint

起点终点都有吗?(提示很重要)

Source

石伟

提交代码