Maze

Time limit2sMemory limit128 MB

Summary

Given a tree-like maze grid, compute the expected number of steps for a random depth-first exploration (choosing unvisited branches uniformly, backtracking on dead ends) to travel from entrance to exit.

Level: Hard8 of 10
Topics: Tree, DFS, Probability, Dynamic programming
Solved: No attempts yet

Problem

An adventurer must pass through a maze from its entrance to its exit. Because the adventurer does not know the maze, whenever a path branches, one of the unvisited paths is chosen uniformly at random. A path that has already been investigated is never treated as new again, and the adventurer only backtracks after deciding that there are no unvisited paths left in the current direction.

The maze has no cycle that returns to the same point, and it has no open area containing a 2×2 block of open cells. There is exactly one entrance and exactly one exit, and both are on the boundary of the maze. Even when the exit is directly beside a path, that direction is treated as one of the choices at a branch.

Compute the expected number of cell-to-cell steps needed for the adventurer to reach the exit from the entrance.

Input

The first line contains the number of test cases n (0 < n ≤ 100).

Each test case is given in the following format.

The first line contains two integers, the maze height h and width w (3 ≤ h, w ≤ 96).
The next h lines each contain a string of length w.
- # is a wall.
- s is the entrance and t is the exit.
- . is a passable path.
Every boundary cell is a wall except for the entrance and the exit.
The entrance and the exit are always on the boundary.

Output

For each test case, output one line containing the expected number of steps from the entrance to the exit, rounded to exactly two digits after the decimal point.

Examples1

Example 1
Input
```
1
3 6
##s###
#....#
#t####
```
Expected output
```
5.00
```