A_W_S_N - Happy Valentine Day (Valentine Maze Game)

Happy Valentine Day!

Valentine Maze

Picture Source: http://www.printactivities.com/Mazes/Shape_Mazes/Heart_Maze.html

In this valentine day, Tjandra Satria Gunawan (TSG) have a mission to date with A** W****** S****** N******(AWSN), Before TSG meet AWSN, TSG want to collect all the chocolate in entire land/maze then share all the chocolate with AWSN later, but AWSN doesn't like to wait, so TSG must collect all chocolate as fast as possible before meet AWSN. Please help TSG to complete this mission. Given a map size m×n (1<m,n≤100), and the map:

'#' denoting wall (TSG can't walk to this area)

'.' denoting road (TSG can walk to this area)

'C' denoting chocolate (also walkable area, appear less than 10 times on the map)

'T' denoting TSG (also walkable area, only appear once on the map)

'W' denoting AWSN (also walkable area, only appear once on the map)

Tjandra can move up, down, left or right, and cost one unit of time every movement.

Input

The first line of input, there's one integer T (T≤30) denoting number of test case, then T case(s) follow,

For each test case:

--> First line contains two integers m and n denoting size of map

--> next m line(s) contains n characters that's the map description.

Output

For each test case, output minimum of time required to complete this mission, if it's impossible to complete this mission, output "Mission Failed!" without quotes.

Example

Input:
8
3 3
T..
...
..W
3 6
######
#T..W#
######
3 6
######
#T#.W#
######
3 6
##C###
#T..W#
######
3 6
C#C###
.T..W#
######
5 10
##########
#T.#.C#..#
#..#..#..#
#..W..#..#
##########
5 10
##########
#T.#.C#.C#
#..#..#..#
#..W..#..#
##########
5 10
##########
#C.#.C#.C#
#..#..#..#
#..T..W..#
##########

Output:
4
3
Mission Failed!
5
9
12
Mission Failed!
23

Time Limit ≈ 5*(My Program (Semi Bruteforce) Speed)

See also: Another problem added by Tjandra Satria Gunawan


Added by:Tjandra Satria Gunawan
Date:2013-02-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:My Love (A_W_S_N) \(^_^)/ I love her since 2008 (when I was studying at EKASMA High School) until present ;-)

hide comments
2013-02-14 03:29:27 (Tjandra Satria Gunawan)(曾毅昆)
Note: All test cases are manually generated, need ~4 hours to make only 30 cases.. (at the begining I plan to make 100 cases, but I'm tired so 30 cases is enough), have fun :-)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.