A. Еще одна игра со строкой
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Гомера есть два друга — Алиса и Боб. Оба они фанаты строк.

Однажды Алиса и Боб решили сыграть в игру на строке $$$s = s_1 s_2 \dots s_n$$$ длиной $$$n$$$, состоящей из строчных английских букв. Они ходят по очереди, Алиса начинает.

В свой ход игрок должен выбрать индекс $$$i$$$ ($$$1 \leq i \leq n$$$), который не был выбран ранее, и поменять $$$s_i$$$ на любую другую строчную английскую букву $$$c$$$, удовлетворяющую $$$c \neq s_i$$$.

Когда все индексы уже были выбраны по одному разу, игра заканчивается.

Цель Алисы — сделать финальную строку лексикографически как можно меньше, в то время как цель Боба — сделать финальную строку лексикографически как можно больше. Оба они являются профессиональными игроками, поэтому всегда играют оптимально. Гомер не является профессиональным игроком, поэтому ему интересно, какой будет финальная строка.

Строка $$$a$$$ лексикографически меньше строки $$$b$$$, если и только если выполняется один из следующих пунктов:

  • $$$a$$$  — префикс $$$b$$$, но $$$a \ne b$$$;
  • в первой позиции, где $$$a$$$ и $$$b$$$ различны, в строке $$$a$$$ находится буква, которая встречается в алфавите раньше, чем соответствующая буква в $$$b$$$.
Входные данные

Каждый тест содержит несколько наборов входных данных. Первая строка содержит $$$t$$$ ($$$1 \le t \le 1000$$$)  — количество наборов входных данных. Описание наборов входных данных приведено ниже.

Единственная строка каждого набора входных данных содержит одну строку $$$s$$$ ($$$1 \leq |s| \leq 50$$$), состоящую из строчных английских букв.

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

Для каждого набора входных данных выведите финальную строку в отдельной строке.

Пример
Входные данные
3
a
bbbb
az
Выходные данные
b
azaz
by
Примечание

В первом наборе входных данных: Алиса делает первый ход и должна поменять единственную букву на другую, поэтому она меняет ее на «b».

Во втором наборе входных данных: Алиса меняет первую букву на «a», затем Боб меняет вторую букву на «z», Алиса меняет третью букву на «a», а затем Боб меняет четвертую букву на «z».

В третьем наборе входных данных: Алиса меняет первую букву на «b», а затем Боб меняет вторую букву на «y».