Blind Maze Escape

XH makes maze toys. The board of this toy is a grid with $N$ rows and $M$ columns. A transparent acrylic sheet covers the top, so you cannot pick the marble out by hand. The outermost rows and columns are closed off, and a single hole is punched somewhere on the border. That hole is the exit.

The player can tilt the board left, right, up, or down. When the board is tilted, the marble rolls in that direction and stops on the last cell before a wall or an obstacle. If it passes the exit while rolling, the marble leaves the board, and after that no tilt changes anything.

The factory stamps out boards of one shape, but the board is shaken during delivery, so before you open the package you do not know which empty cell holds the marble. The marble can be on any empty cell. Find a sequence of tilts that removes the marble without opening the package, that is, without seeing where the marble is. One sequence has to work from every empty cell the marble could start on.

The first line contains the number of test cases $T$.

The first line of each test case contains the board height $N$ and width $M$. ($3 \le N, M \le 10$)

Each of the next $N$ lines contains a string of length $M$ describing the board. The string uses only '.', '#', and 'O'. A '.' is an empty cell, a '#' is a wall or an obstacle the marble cannot pass, and an 'O' is the exit punched in the border.

Every board has only '#' on its border except for the exit. There is at least one empty cell. From every empty cell there is a path to the exit that steps only on empty cells sharing an edge.

Print one line for each test case.

If the marble can always be removed within 10 tilts no matter which empty cell it starts on, print the shortest such sequence of tilts as a string of 'L', 'R', 'U', and 'D'. The four letters mean tilting left, right, up, and down, in that order.

If several shortest sequences work, print the one that comes first in lexicographic order. Lexicographic order uses the letter order D < L < R < U.

If the marble cannot be removed within 10 tilts, print XHAE.