The maze is the same as problem D, and I strongly recommend you solve the previous one first because it's easier than this. This time, we want you design the command for our poor robot to move from where it is to its destination. The command sequence's length should be the shortest. If several solutions exist, find the lexicographically minimum one. Lexicographical sequence is the order in one dictionary. For example, "\textbf{cat}" is less than "\textbf{do}", and "\textbf{do}" is less than "\textbf{dog}". \InputFile The first line contains a single integer \textbf{T}, indicating the number of test cases. Each test case begins with one integer \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{50}), indicating the size of the maze. The followed \textbf{N} lines are \textbf{N} strings whose length is also \textbf{N}, indicating the maze. \OutputFile For each case, output a command string if there is a solution, otherwise output \textbf{-1}.