Maze Stretching

Input

The first line contains the number of test cases. For each test case, the first line contains two numbers $L$ and $N$, where $L$ is the required length of the shortest path and $N$ is the number of lines describing the maze. The following $N$ lines describe the maze, with each line representing one row of the maze (each row's length is the horizontal dimension of the maze).

Output

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

Case #$K$: $P$%

• $P$ must have a leading zero if it is between $0$ and $1$.

• $P$ must be rounded to $3$ decimal places, and always formatted with $3$ decimal places (with trailing zeros if necessary).

Constraints

- The height and width of the maze are at most $100$ cells. - All lines describing one maze are the same length. - There is always a solution. - 0.000 \leq P \leq 1000.000 - There will be no direct horizontal-only path connecting S to E. (The result is always unique).

Explanation of the first test case in the example: In the original maze, the length of the shortest path is $3$ because there are two horizontal steps and one vertical step. Our goal is to make the shortest path length $2.5$, so the vertical dimension must be stretched with a percentage value less than $100$. In this case, it is $50\%$, which means the vertical distance between two cells becomes $0.5$.

Examples