Дана строка $$$s$$$, состоящая из строчных латинских букв. Каждая буква встречается в ней не более двух раз.
Ваша задача — переупорядочить буквы в строке так, чтобы для каждой пары букв, которые встречаются ровно дважды, расстояния между буквами в паре одинаковое. Не разрешается добавлять или удалять буквы.
Можно показать, что ответ всегда существует. Если существует несколько ответов, выведите любой из них.
В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных.
Каждый набор входных данных содержит одну непустую строку $$$s$$$, состоящую из строчных латинских букв. Каждая буква встречается в строке не более двух раз. Длина строки не превосходит $$$52$$$.
На каждый набор входных данных выведите одну строке. Каждая буква должна входить в нее столько же раз, сколько и в строку $$$s$$$. Для каждой пары букв, которые встречаются ровно дважды, расстояния между буквами в паре должно быть одинаковое.
Если существует несколько ответов, выведите любой из них.
3oelhlabcdcbaac
hello ababcdc ac
В первом наборе входных данных единственная буква, которая встречается ровно дважды — это буква 'l'. Можно переупорядочить буквы как угодно, потому что расстояния не с чем сравнивать.
Во втором наборе входных данных буквы, которые встречаются ровно дважды — это 'a', 'b' и 'c'. Изначально буквы 'a' находятся на расстоянии $$$6$$$, буквы 'b' находятся на расстоянии $$$4$$$, а буквы 'c' находятся на расстоянии $$$2$$$. Они не одинаковые, поэтому надо буквы переупорядочить. После изменения буквы 'a' находятся на расстоянии $$$2$$$, буквы 'b' находятся на расстоянии $$$2$$$ и буквы 'c' находятся на расстоянии $$$2$$$. Они одинаковые, поэтому ответ корректен.
В третьем наборе входных данных нет букв, которые встречаются ровно дважды. Поэтому любой порядок подходит. В том числе оригинальная строка без изменений.
