A. Баланс AB
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана строка $$$s$$$ длины $$$n$$$, состоящая из букв a и/или b.

Пусть $$$\operatorname{AB}(s)$$$ — это количество вхождений строки ab в $$$s$$$ как подстроки. Аналогично, $$$\operatorname{BA}(s)$$$ — это количество вхождений ba в $$$s$$$ как подстроки.

За один шаг, вы можете выбрать индекс $$$i$$$ и заменить $$$s_i$$$ на букву a или b.

Какое наименьшее количество шагов нужно сделать, что бы достигнуть строки в которой $$$\operatorname{AB}(s) = \operatorname{BA}(s)$$$?

Напоминание:

Количество вхождений строки $$$d$$$ в $$$s$$$ как подстроки — это количество индексов $$$i$$$ ($$$1 \le i \le |s| - |d| + 1$$$) таких, что подстрока $$$s_i s_{i + 1} \dots s_{i + |d| - 1}$$$ равна $$$d$$$. Например, $$$\operatorname{AB}($$$aabbbabaa$$$) = 2$$$ так как есть ровно два индекса $$$i$$$: $$$i = 2$$$ с aabbbabaa и $$$i = 6$$$ с aabbbabaa.

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

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

В первой и единственной строке каждого набора задана одна строка $$$s$$$ ($$$1 \le |s| \le 100$$$, где $$$|s|$$$ — это длина строки $$$s$$$), состоящая только из букв a и/или b.

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

Для каждого набора входных данных, выведите результирующую строку $$$s$$$, в которой $$$\operatorname{AB}(s) = \operatorname{BA}(s)$$$, и которую вы получите, сделав наименьшее возможное количество ходов.

Если существует несколько ответов, выведите любой из них.

Пример
Входные данные
4
b
aabbbabaa
abbb
abbaab
Выходные данные
b
aabbbabaa
bbbb
abbaaa
Примечание

В первом наборе входных данных, и $$$\operatorname{AB}(s) = 0$$$, и $$$\operatorname{BA}(s) = 0$$$ (строка ab (ba) ни разу не входит в строку b). А потому мы можем оставить $$$s$$$ нетронутой.

Во втором наборе, $$$\operatorname{AB}(s) = 2$$$ и $$$\operatorname{BA}(s) = 2$$$. Строку $$$s$$$ можно оставить нетронутой.

В третьем наборе, $$$\operatorname{AB}(s) = 1$$$ и $$$\operatorname{BA}(s) = 0$$$. Можно, например, заменить $$$s_1$$$ на b, сделав оба значения равными нулю.

В четвертом наборе, $$$\operatorname{AB}(s) = 2$$$ и $$$\operatorname{BA}(s) = 1$$$. Можно, например, заменить $$$s_6$$$ на a, сделав оба значения равными $$$1$$$.