Drak Brak

Až hen na polnočnej strane, v zemi poľskej, žije v horách drak menom Brak. A ten drak na jednej náhornej plošine ukryl svoj poklad. Ak ho chcete získať, budete sa k nemu musieť dostať, a to podľa drakovych pravidiel.

Plošina má tvar obdlžnika a je rozdelená na niekoľko rovnako veľkých štvorcov. Drak rozhodol, v ktorom štvorci musíte začať a kam umiestni poklad. V jednom kroku sa vždy môžete presunúť na niektorý z (najviac) štyroch susedných štvorcov.

Na niektorých štvorcoch má drak pazúrom v blate vyryté poznámky z Vybraných partií komplexnej analýzy. Ak mu ich postúpite, rovno Vás zožerie.

Okrem toho je drak starý a netrpezlivý, takže ak Vaša cesta k pokladu nebude najkratšia možná, omrzí ho dívať sa na Vás a zožerie Vás aj tak.

A ako keby ani to nestačilo, drak je hrozný pedant. Preto ho neuveriteľne naštvete, ak k pokladu pôjdete nesystematicky. Zo všetkých možných (najkratších) ciest si musíte vybrať tú, ktorej drakov zápis bude lexikograficky najmenší (t.j. prvý v abecednom poradí).

Drakov zápis cesty je jednoduchý: pre každý Váš krok si zapíše jedno písmenko, hovoriace, ktorým smerom ste sa na mape pohli: hore je G (w gór), dole je D (w dól), doľava je L (w lewo) a doprava je P (w prawo).

Vstup

V prvom riadku je malé celé číslo $T$, udávajúce počet máp, ktoré nasledujú. Každá z nich vyzerá nasledovne:

V prvom riadku sú dve celé čísla $R$ a $S$ $(1 \leq R, S \leq 1000)$ ­— počet riadkov a stĺpcov mapy. Nasleduje $R$ riadkov obsahujúcich mapu. Každý z nich obsahuje $S$ znakov. Význam znakov je nasledovný:

• . - prázdny štvorec
• X - popísaný štvorec, na ktorý nesmiete stúpiť
• S - štvorec, kde začínate
• * - štvorec, kde je poklad

Výstup

Pre každú mapu vypíšte jeden riadok s reťazcom, ktorý zodpovedá hľadanej ceste. Ak žiadna cesta neexistuje, vypíšte namiesto jej popisu reťazec BRAK.

Príklad

1
5 6
....*.
..XX..
...X..
S.....
......

GGGPPPP