Happy Valentine Day!

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