Treasure

In an old inn you have just acquired a map that will lead you to Montezuma's fabled treasure. It turns out the Aztecs hid the treasure on a plateau in the Andes — the land of the Incas. The plateau is shaped like a rectangle and is riddled with dangerous chasms. The map marks the position from which the search must begin and the position of the treasure.

The map is given as a grid of $w \times k$ characters. From a given cell you may move to the cell on the left, on the right, up, or down. You want to find a path to the treasure that avoids the chasms, and it must be the shortest one. Moreover, so that the treasure hunter is not caught by Montezuma's curse, they must reach the treasure along the shortest path that — when written as a string of the characters L, P, G, D (corresponding to moving left, right, up, and down respectively) — comes first in lexicographic order.

Searching for this path by hand would be far too tedious, so you decide to write a program that does it for you.

The first line of the input contains a small integer — the number of data sets that follow one after another. Each data set is described as follows.

The first line contains two integers $w$ and $k$ ($1 \le w, k \le 1000$): the number of rows and the number of columns of the map, respectively. Each of the next $w$ lines contains $k$ characters — the contents of the map. The characters mean:

• . — an ordinary part of the plateau
• X — a part of the plateau containing a chasm
• S — your starting position
• * — the position of the treasure

For each data set, print on a single line the description of the shortest path from the starting position to the treasure. If there are several such paths, print the one that comes first in lexicographic order. If the treasure cannot be reached from the starting position, print the word BRAK.