Tower Defence

Tower Defence is a popular classic game. During the game, there will appear some monsters at the entry and each will find a shortest path to the exit. Your task is puting some warriors on the map to kill the monsters before they reach exit.

You could put warrior(infinite) on the map to change the pathes of monsters. Of course, the longer the path is, the more advantageous to you.
Now, giving you the information of the map, how do you put the warriors to make the monsters move on the longest path?
The meaning of each character in the map:
'S' represents the entry of the map, one and only one;
'T' represents the exit of the map, one and only one;
'.' represents the grid that monster could move on;
'B' represents the barrier that monster couldn't move on;
'W' represents the warrior that you put.(could only put on '.')

The first line is a number T(1<=T<=30), represents the number of case. The next T blocks follow each indicates a case.
The first line of each case contains two integers N, M (3<=N<=20 , 3<=M<=9)
Then N lines follow, each line contains M chars represent the map, include 'S','T','.','B'.
I promise there must be at least one way from entry to exit.

For each case, first line output the number of case with the longest distance from S to T.(as shown in the sample output)
Then output any one of these ways, using the same format for the map as in the input. Output a blank line after each case.(Special judge.If you not output a blank line after each case, you will get Wrong Answer)

4
3 3
S..
...
..T

5 5
S....
.B.B.
.....
.B.B.
....T

5 5
S...T
..B..
..B..
..B..
.....

5 5
S...T
..B..
..B..
..B..
..B..

Case 1: 5
S..
...
..T

Case 2: 17
S....
WBWB.
.....
.BWBW
....T

Case 3: 17
S.W.T
W.B.W
..B..
.WBW.
.....

Case 4: 5
S...T
..B..
..B..
..B..
..B..

NotOnlySuccess

2011 Alibaba Programming Contest