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

Вам задано длинное число $$$a$$$, состоящее из $$$n$$$ цифр ($$$n$$$ от $$$1$$$ до $$$3 \cdot 10^5$$$ включительно). Оно может содержать лидирующие нули.

Вы можете поменять местами две соседние цифры, если они имеют разную четность (т.е. они имеют разный остаток от деления на $$$2$$$).

Например, если $$$a = 032867235$$$ вы можете получить следующие числа за одну операцию:

  • $$$302867235$$$ если поменяете местами первую и вторую цифры;
  • $$$023867235$$$ если поменяете местами вторую и третью цифры;
  • $$$032876235$$$ если поменяете местами пятую и шестую цифры
  • $$$032862735$$$ если поменяете местами шестую и седьмую цифры;
  • $$$032867325$$$ если поменяете местами седьмую и восьмую цифры.

Обратите внимание, что вы не можете поменять местами цифры на позициях $$$2$$$ и $$$4$$$, потому что эти позиции не соседние. Так же, вы не можете поменять местами цифры на позициях $$$3$$$ и $$$4$$$, потому что эти цифры имеют одинаковую четность.

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

Найдите минимальное число, которое вы можете получить.

Обратите внимание, что ответ так же может содержать лидирующие нули.

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

Первая строка содержит число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Единственная строка каждого набора содержит длинное число $$$a$$$, его длина $$$n$$$ в отрезке от $$$1$$$ до $$$3 \cdot 10^5$$$ включительно.

Гарантируется, что сумма всех $$$n$$$ не превосходит $$$3 \cdot 10^5$$$.

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

На каждый набор входных данных выведите ответ — минимальное число, которое вы можете получить.

Пример
Входные данные
3
0709
1337
246432
Выходные данные
0079
1337
234642
Примечание

В первом наборе вы можете выполнить следующую последовательность операций (пара цифр, которую вы меняете местами, выделена): $$$0 \underline{\textbf{70}} 9 \rightarrow 0079$$$.

Во втором наборе изначальное число является оптимальным.

В третьем наборе вы можете выполнить следующую последовательность операций: $$$246 \underline{\textbf{43}} 2 \rightarrow 24 \underline{\textbf{63}}42 \rightarrow 2 \underline{\textbf{43}} 642 \rightarrow 234642$$$.