Martian Pits

A rover must travel from its start cell to its destination on a grid map of the Martian surface. Recently, pranksters have dug a number of pits into the surface, and the rover must not fall into any of them. Reaching the destination may therefore require long detours, or may even be impossible.

You control the rover with one command per second. The rover has a facing direction and a forward speed, measured in cells per second. It begins stopped (speed 0) and facing up. Each second you issue exactly one command:

• Forward — only when the rover is stopped: it starts rolling forward at speed 1.
• Backward — only when the rover is stopped: it starts rolling backward at speed 1.
• Faster — only while the rover is moving forward: increase the forward speed by 1, up to a maximum of 5.
• Slower — only while the rover is moving forward: decrease the forward speed by 1, down to 0.
• Stop — the rover's speed immediately becomes 0.
• Left / Right — only when the rover is stopped: turn the rover 90° to the left or right, in place.
• Wait — nothing changes.

A command whose precondition is not met (for example, Forward while already moving) has no effect. After the command is applied, the rover advances for that one second at its current speed, covering that many cells in the direction it faces (or the opposite direction when moving backward). Every cell the rover passes over, including the cell where it ends the second, must be empty and inside the map; a command that would send the rover across a pit or off the edge of the map is not allowed.

The map is described with the characters . for empty space, P for a pit, R for the rover's starting cell, and D for the destination. R and D each appear exactly once. The rover always starts facing up. The direction it faces at the destination does not matter, but it must be stopped there. Find the fewest seconds in which the rover can reach the destination and stop, or report that it is impossible.

The first line contains the number of data sets, $K$. Each data set follows, in this form:

The first line contains two integers $h$ and $w$ with $1 \le h, w \le 50$ — the height and width of the map.

The next $h$ lines each contain $w$ characters describing one row of the map, using the characters described above.

For each data set, output a line reading Data Set x:, where x is the number of the data set (starting from 1). On the following line, output the minimum number of seconds in which the rover can reach the destination and stop. If the destination cannot be reached, output Impossible instead.

Print a blank line between consecutive data sets.