Doing Smart Work

You may swap adjacent digits of different parity any number of times; find the smallest number you can obtain, with leading zeros allowed.

输入格式

The first line contains t; then t lines of digit strings follow. Added by this site: t≤10000, total length ≤200000.

输出格式

For each test case, output the smallest digit string on its own line.

样例 1

输入：

1
4321

输出：

3142

样例 2

输入：

3
97531
02468
9081726354

输出：

97531
02468
0826491735

样例 3

输入：

2
1203
5550

输出：

1203
0555