Maze Escape with One Wall Break

You are given a maze represented as a grid with N rows and M columns. Each cell in the grid can either be a path denoted by . or a wall denoted by #. Ryan starts at the top‐left corner (cell (0, 0)) and must reach the bottom‐right corner (cell (N-1, M-1)).

You are allowed to move one step at a time in one of the four directions: up, down, left, or right. Moreover, you have the option to break through at most one wall (i.e. change one # cell into a traversable path) if needed.

Your task is to compute the minimum number of steps required to reach the destination. If it is impossible for Ryan to reach the destination even after breaking one wall, output Impossible.

The problem can be modeled using the Breadth-First Search (BFS) algorithm with a slight modification to handle the extra state regarding whether the wall break is still available.

The relationship between the path length and the steps is given by the formula below:

\(steps = \min_{\text{all valid paths}}\{\text{number of moves}\}\)

inputFormat

The input is read from stdin and has the following format:

• The first line contains an integer T, the number of test cases.
• For each test case, the first line contains two integers N and M separated by space.
• This is followed by N lines, each containing a string of length M composed of . and #, representing the maze grid.

outputFormat

For each test case, output on a new line the minimum number of steps required to reach the bottom‐right corner from the top‐left corner. If it is impossible, output Impossible.

The output should be written to stdout.

## sample

1
5 5
.....
.###.
.#.#.
.#.#.
....#

8

</p>