Maze Stretching

Normally a path through a maze is measured as the number of steps taken from the start to the end, where each step covers a distance of exactly 1. Suppose instead that we may stretch the maze along its vertical dimension (north-south), either shortening or extending it. Stretching only changes the distance covered by a step between two vertically adjacent cells: such a step now covers a distance of $X$ instead of 1. Horizontal steps (east-west) always cover a distance of 1.

The maze is a two-dimensional grid where # marks a wall, S marks the starting cell, and E marks the ending cell; every other cell is open. You may move between orthogonally adjacent open cells.

Because of outside conditions, the shortest path from S to E must be made to have length exactly $L$. You may not change the layout of the maze, and you may not change anything in the horizontal dimension. You may only stretch the vertical dimension, by any percentage.

The stretch percentage $P$ is the length of a single vertical step expressed as a percentage: a vertical step covers a distance of $P / 100$ (so $X = P / 100$). Find the percentage $P$ for which the shortest path of the maze becomes exactly $L$.

The first line contains the number of test cases. Each test case begins with a line containing two numbers $L$ and $N$, where $L$ is the required length of the shortest path and $N$ is the number of lines that describe the maze. The following $N$ lines describe the maze, one row per line. The length of each row is the horizontal dimension of the maze.

For each test case, output the stretch percentage in the following format:

Case #K: P%

where K is the test case number, starting from 1. $P$ must have a leading zero when its value is between 0 and 1. $P$ is rounded to 3 decimal places and always printed with exactly 3 decimal places (adding trailing zeros when needed).

The height and width of the maze are each at most 100 cells.

All lines describing a single maze have the same length.

There is always a solution.

The result is between 0.000 and 1000.000, inclusive.

There is never a path connecting S and E that moves only horizontally, so the result is always unique.

Consider a maze whose shortest path takes two horizontal steps and one vertical step, giving a natural length of 3. To make the shortest path have length 2.5, the single vertical step must cover a distance of 0.5, which corresponds to stretching the vertical dimension to 50%.