1 #include<iostream>
 2 #include<string>
 3 #include<queue>
 4 #include<stack>
 5 #include<vector>
 6 #include<map>
 7 #include<cstdio>
 8 #include<cstdlib>
 9 #include<algorithm>
10 #include<set>
11 #include<list>
12 #include<iomanip>
13 #include<cstring>
14 #include<cmath>
15 #include<limits>
16 using namespace std;
17 
18 #define au auto
19 #define debug(i) cout<<"<debug> "<<i<<"<\debug>"<<endl
20 #define mfor(i,a,b) for(register int i=(a);i<=(b);i++)
21 #define mrep(i,a,b) for(register int i=(a);i>=(b);i--)
22 #define LLL __int128
23 #define Re register
24 #define il inline
25 #define mem(a,b) memset(a,(b),sizeof(a))
26 typedef pair<int, int> intpair;
27 typedef long long int LL;
28 const int INF = 0x3f3f3f3f;
29 const long long int INFLL = 0x3f3f3f3f3f3f3f3f;
30 
31 const int maxn = 100010;
32 
33 int n;
34 int T;
35 int a[maxn];
36 
37 int main()
38 {
39     cin >> T;
40     while (T--)
41     {
42         string s;
43         cin >> s;
44         vector<int>odd;
45         vector<int>even;
46         string ans;
47         mfor(i, 0, s.length() - 1)
48         {
49             if (s[i] - '0' & 1) odd.push_back(s[i] - '0');
50             else even.push_back(s[i] - '0');
51         }
52         int cnte = 0, cnto = 0;
53         while (cnte < even.size() && cnto < odd.size()) 
54         {
55             if (even[cnte] < odd[cnto])
56             {
57                 ans.push_back(even[cnte] + '0');
58                 cnte++;
59             }
60             else 
61             {
62                 ans.push_back(odd[cnto] + '0');
63                 cnto++;
64             }
65         }
66         while (cnto < odd.size()) 
67         {
68             ans.push_back(odd[cnto] + '0');
69             cnto++;
70         }
71         while (cnte < even.size()) 
72         {
73             ans.push_back(even[cnte] + '0');
74             cnte++;
75         }
76         cout << ans << endl;
77     }
78 }

View Code