提示: 欢迎访问OurACM平台
Problem 1073 Raiders of the Lost Ark

Accept: 288    Submit: 578
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

In this famous film, renowned archeologist and expert in the occult, Dr. Indiana Jones, is hired by the U.S. Government to find the Ark of the Covenant, which is believed to still hold the ten commandments. Unfortunately, agents of Hitler are also after the Ark. Dr. Jones escapes from various close scrapes in a quest that takes him from Nepal to Cairo. Your task is to help him to find the lost Ark of the Covenant in the maze earlier than the enemy.

There are several barriers in the maze, Dr. Jones can bypass these barriers on foot or by jump .He can go on foot in four directions of east, south, west and north to reach a neighboring position. He can also jump cross a cell in the directions of southeast, southwest, northeast and northwest to reach a new position. The following figure shows Dr. Jones's action where O denotes the original position and X denotes the new possible positions after one action.

Input

The first line of the input is an integer n (0<=n<=20), denoting the number of test cases. The following lines are the data of n test cases. The first line of each test case consists of two integer x and y (0<x<10, 0<y<10). The next x lines describe the maze matrix, which contains x rows and y columns. In the matrix, 'W' denotes the barrier, 'B' denotes the enterable position, 'S' denotes the starting position, and 'X' denotes the position of the ark. There have and only have one 'S' and one 'X' in a maze matrix.

Output

For each test case, output one line. If there is a solution for the problem, output the number of the least steps to find the Ark. Otherwise output "NO ANSWER".

Sample Input

3 3 3 SWB BWB XBB 5 4 BXWB BBWS BBWB BBWB BBBB 3 2 WX WW WS

Sample Output

2 2 NO ANSWER

Source

FJNUPC 2005

Submit  Back  Status  Discuss