Недавно вы купили робота-снегохода и принесли его домой. Ваш дом — это клетка $$$(0, 0)$$$ на бесконечной координатной сетке.

Вы также получили последовательность инструкций этого робота. Она записана в виде строки $$$s$$$, состоящей из символов 'L', 'R', 'U' и 'D'. Если сейчас робот находится в клетке $$$(x, y)$$$, он может передвинуться в одну из смежных клеток (зависит от текущей инструкции).

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

Вы заметили предупреждение на последней странице руководства: если робот посетит какую-то клетку (кроме $$$(0, 0)$$$) дважды, то он сломается.

Таким образом, последовательность инструкций является корректной, если робот начинает в клетке $$$(0, 0)$$$, выполняет заданные инструкции, не посещает никакую клетку, кроме $$$(0, 0)$$$, два или более раз и заканчивает свой путь в клетке $$$(0, 0)$$$. Также клетка $$$(0, 0)$$$ должна быть посещена не более двух раз: в начале и в конце (если путь пустой, то она будет посещена только единожды). Например, следующие последовательности инструкций являются корректными: «UD», «RL», «UUURULLDDDDLDDRRUU», а следующие являются некорректными: «U» (конечная клетка не равна $$$(0, 0)$$$) и «UUDD» (клетка $$$(0, 1)$$$ посещается дважды).

Но изначальная последовательность инструкций может быть некорректной. Вы не хотите, чтобы ваш робот сломался, поэтому вы решили перепрограммировать его следующим образом: вы удалите какие-то (возможно, все или никакие) инструкции из изначальной последовательности инструкций, затем поменяете порядок оставшихся инструкций так, как хотите, и включите вашего робота, который начнет движение.

Ваша задача — удалить минимальное количество инструкций из изначальной последовательности и поменять порядок оставшихся инструкций таким образом, чтобы последовательность стала корректной. Вам необходимо вывести максимальную по длине корректную последовательность инструкций, которую вы можете получить.

Заметьте, что вам необходимо выбрать любой порядок оставшихся инструкций (нет необходимости минимизировать количество обменов или какую-либо другую похожую метрику).

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