Вам задано длинное число a, состоящее из n цифр (n от 1 до 3⋅105 включительно). Оно может содержать лидирующие нули.
Вы можете поменять местами две соседние цифры, если они имеют разную четность (т.е. они имеют разный остаток от деления на 2).
Например, если a=032867235 вы можете получить следующие числа за одну операцию:
Обратите внимание, что вы не можете поменять местами цифры на позициях 2 и 4, потому что эти позиции не соседние. Так же, вы не можете поменять местами цифры на позициях 3 и 4, потому что эти цифры имеют одинаковую четность.
Вы можете выполнять любое (возможно, нулевое) количество таких операций.
Найдите минимальное число, которое вы можете получить.
Обратите внимание, что ответ так же может содержать лидирующие нули.
Первая строка содержит число t (1≤t≤104) — количество наборов входных данных.
Единственная строка каждого набора содержит длинное число a, его длина n в отрезке от 1 до 3⋅105 включительно.
Гарантируется, что сумма всех n не превосходит 3⋅105.
На каждый набор входных данных выведите ответ — минимальное число, которое вы можете получить.
3 0709 1337 246432
0079 1337 234642
В первом наборе вы можете выполнить следующую последовательность операций (пара цифр, которую вы меняете местами, выделена): 070_9→0079.
Во втором наборе изначальное число является оптимальным.
В третьем наборе вы можете выполнить следующую последовательность операций: 24643_2→2463_42→243_642→234642.
