H. Покраска строки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Формально, выпишем

  • строку $$$r$$$ (может быть пустой) — все красные буквы в порядке слева направо (красная подпоследовательность),
  • строку $$$b$$$ (может быть пустой) — все синие буквы в порядке слева направо (синяя подпоследовательность).

Ваша задача придумать такую покраску, что $$$\max(r, b)$$$ — минимален. Небольшое напоминание: пустая строка является лексикографически наименьшей.

Входные данные

В первой строке записано целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных в тесте. Далее записаны сами наборы входных данных по одному в строке.

Каждый набор входных данных является непустой строкой $$$s$$$ длины от $$$2$$$ до $$$100$$$ символов включительно, которая состоит из строчных букв латинского алфавита.

Выходные данные

Выведите $$$t$$$ строк, $$$i$$$-я из них должна содержать ответ на $$$i$$$-й набор входных данных. Выведите строку длины $$$n$$$, где $$$n$$$ — длина заданной строки $$$s$$$: $$$j$$$-й символ строки должен быть равен либо 'R', либо 'B' в зависимости от того в красный или синий цвет покрашен $$$j$$$-й символ строки в найденном решении. Если ответов несколько, выведите любой из них.

Пример
Входные данные
5
kotlin
codeforces
abacaba
ffccgc
yz
Выходные данные
RRRRBB
RRRRRRRBBB
RRRRBBB
RBBBBR
RR