Знову Лабіринт
Лабіринт такий самий, як у задачі D, і я настійно рекомендую вам спочатку вирішити попередню, оскільки вона легша за цю.
Цього разу ми хочемо, щоб ви розробили команду для нашого бідного робота, щоб він перемістився з місця, де він знаходиться, до місця призначення. Довжина послідовності команд повинна бути найкоротшою. Якщо існує кілька рішень, знайдіть лексикографічно мінімальне. Лексикографічна послідовність — це порядок в одному словнику. Наприклад, "cat" менше ніж "do", а "do" менше ніж "dog".
Вхідні дані
Перша строка містить одне ціле число T, що вказує на кількість тестових випадків.
Кожен тестовий випадок починається з одного цілого числа N (1 ≤ N ≤ 50), що вказує на розмір лабіринту. Наступні N рядків є N рядками, довжина яких також N, що вказують на лабіринт.
Вихідні дані
Для кожного випадку виведіть рядок команд, якщо є рішення, інакше виведіть -1.