Chuck's Challenge

Chuck's Challenge is a game in which a player navigates a maze made of tiles in a grid. The player may find doors that can be unlocked with keys collected along the way. Write a program that determines the minimum number of doors that must be opened to reach the exit of the maze.

Rules

• Tiles that are diagonal to each other are not adjacent. Only up, down, left, and right count.
• The player begins the maze on the entrance tile.
• The player may only visit passable tiles that are adjacent to the tile the player is currently visiting.
• A door stays impassable until the player has visited a tile with the matching key ('A' matches 'a', 'B' matches 'b', and so on).
• At first, unstable floors are passable. If the player leaves an unstable floor and visits any other type of tile, that floor becomes impassable.
• When an unstable floor becomes impassable, all adjacent unstable floors become impassable too.
• The outer edge of the maze is an impassable wall.

The first line contains the number of test cases $T$ ($1 \le T \le 50$). Each test case begins with a line containing two integers $R$ and $C$ ($4 \le R, C \le 50$). The next $R$ lines each contain a row of $C$ characters describing the maze. Only the characters listed in the table above appear in the maze.

For each test case, print one line containing the minimum number of doors that must be opened to reach the exit. If the exit cannot be reached, print "Impossible".