Jury Jeopardy

What would a programming contest be without an ASCII maze problem? One of the judges wrote one.

The maze has exactly one square that is both the entrance and the exit, it contains no cycles, and it has no empty space completely enclosed by walls. A robot is sent in to explore the whole maze. The robot always faces the direction it travels in. At every step the robot first tries to turn right. If there is a wall there, it tries to go forward instead. If that is blocked as well, it turns left. If all three directions are blocked, it turns back.

The original task was to print the path of the robot, starting from the entrance square until it comes back to that square. Every move is written as one letter: 'F' is forward, 'L' is left, 'R' is right and 'B' is backward. 'L', 'R' and 'B' describe the change of orientation and also an advance of one square in that direction. The robot starts out facing east, and the path always ends on the entrance square.

The judge in charge had finished the samples and the test data when the input file was deleted, with no way to recover it. The output and the samples are still there. Reconstruct the input from the output. The judge did write the number of test cases back in by hand.

On the first line one positive integer: the number of test cases, at most 100. After that, per test case:

• one line with a single string, the movements of the robot through the maze.

Every given string is a path that a robot really produced in some maze satisfying the conditions in the output section.

On the first line the number of test cases. After that, per test case:

• one line with two space separated integers $h$ and $w$ ($3 \le h, w \le 100$), the height and the width of the maze.
• $h$ lines of $w$ characters describing the maze, where '#' is a wall and '.' is an empty square.

The entire contour of the maze consists of walls, with the exception of one square on the left side, which is the entrance. The maze contains no cycles and no empty square that cannot be reached from the entrance. Every row and every column, apart from the top row, the bottom row and the rightmost column, contains at least one empty square. Exactly one maze satisfies all of this, so print that maze.