На координатной плоскости стоит робот. Изначально он расположен в точке $$$(0, 0)$$$. Его путь описывается строкой $$$s$$$ длины $$$n$$$, состоящей из символов 'L', 'R', 'U', 'D'.

Каждый из этих символов соответствует некоторому ходу:

• 'L' (влево): робот перемещается из точки $$$(x, y)$$$ в точку $$$(x - 1, y)$$$;
• 'R' (вправо): робот перемещается из точки $$$(x, y)$$$ в точку $$$(x + 1, y)$$$;
• 'U' (вверх): робот перемещается из точки $$$(x, y)$$$ в точку $$$(x, y + 1)$$$;
• 'D' (вниз): робот перемещается из точки $$$(x, y)$$$ в точку $$$(x, y - 1)$$$.

Компания, которая создала этого робота, попросила вас оптимизировать путь робота некоторым образом. Чтобы сделать это, вы можете удалить любую непустую подстроку пути. Но эта компания не хочет, чтобы покупатели заметили перемену в поведении робота. Это означает, что если до оптимизации робот заканчивал свой путь в точке $$$(x_e, y_e)$$$, то после оптимизации (т.е. удаления некоторой единственной подстроки из $$$s$$$) робот тоже должен заканчивать свой путь в точке $$$(x_e, y_e)$$$.

Эта оптимизация — малобюджетный проект, поэтому вам нужно удалить кратчайшую возможную непустую подстроку, чтобы оптимизировать путь робота так, что конечная точка его пути не изменится. Возможна ситуация, когда вы не можете оптимизировать путь. Кроме того, возможно, что после оптимизации полученный путь станет пустой строкой (т.е. удаленная подстрока — это вся строка $$$s$$$).

Напомним, что подстрока строки $$$s$$$ — это такая строка, которая может быть получена из $$$s$$$ с помощью удаления некоторого числа символов (возможно, нулевого) из префикса и некоторого количества символов (возможно, нулевого) из суффикса. Например, подстроками «LURLLR» являются «LU», «LR», «LURLLR», «URL», но не «RR» и «UL».

Вам нужно ответить на $$$t$$$ независимых наборов входных данных.