SP22740 AVMG1 - Another Valentine Maze Game (1D)

**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, I'm very happy to know that many SPOJ user happy to help me on my old Valentine Maze Game (2 years ago). I can't imagine what happen if no one guide me in the maze to meet her (my love), of course it will be much worse, because I can lost in the maze for long time. Now, can you help me again to compute what is expected time needed to meet her in the maze if I just walk uniform randomly on all possible dirrection without any guide? I will be very grateful for your help. For simplicity, in this problem there will be no Chocolate, Wall, and the Maze will be 1 Dimension only. Given a map length **l**, containing 3 possible elements: **'.'** denoting road (I can walk on this area) **'T'** denoting my position (Tjandra) at start (time 0), only appear once on the map. **'W'** denoting Woman I want to meet (Destination), only appear once on the map. Tjandra always walk one step left or right (if valid, valid = I still inside the maze) for each unit of time with equal probability, I never stop until I arrive on my destination.

On the first line, there is an integer **t** denoting number of test cases. Number of test case will be less than or equal to 250. For each test case there are two lines, the first one there is an integer **l** denoting length of map. Length of map will be less than or equal 50. Next line there are **l** characters, each character is element of map that has been described above.

For each test case, output expected time required for me to meet her if I just walk uniform randomly on all possible dirrection. Your answer are considered correct if **absolute error** with judge (my) solution is **less than 10 $ ^{-5} $** . It's guaranteed that my solution has absolute difference less than 10 $ ^{-19} $ with exact answer.