SP13738 A_W_S_N - Happy Valentine Day (Valentine Maze Game)

**Happy Valentine Day!**  Picture Source: [http://www.printactivities.com/Mazes/Shape\_Mazes/Heart\_Maze.html](http://www.printactivities.com/Mazes/Shape_Mazes/Heart_Maze.html "VMaze Source") 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

The first line of input, there's one integer **T** (**T**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.

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