#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
const int INF = 4e5;
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
           
#define time__(d) \
    for ( \
        auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); \
        blockTime.second; \
        debug("%s: %lld ms\n", d, chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false \
    )


int get_num(int l[10],int y){
	int i;
	pi lp[10];
	for(i=0;i<=9;i++){
		lp[i]={l[i],i};
	}
	sort(lp,lp+10);
	for(auto [pos,el] : lp){
		if(pos!=INF && el>y){
			return el;
		}
	}
	return -1;
}
string run_filter(string x,int par){

	int n = x.length(),i,j;
	int leftmost_min[10];
	for(i=0;i<10;i++)
		leftmost_min[i]=INF;
	for(i=0;i<n;i++){
		leftmost_min[(x[i]-'0')]=min(leftmost_min[(x[i]-'0')],i);
		if(i>0 && ((x[i]-'0')%2==par) && ((x[i-1]-'0')%2!=par)){
			//cout<<x<<" "<<i<<" "<<x[i]<<endl;
			int cur=i,go;
		    go = get_num(leftmost_min,(x[i]-'0'));
			if(go!=-1){
				while(i>leftmost_min[go] && (x[i-1]%2)!=par){
					swap(x[i],x[i-1]);
					--i;
				}
				for(j=0;j<10;j++)
					leftmost_min[j]=INF;
				++i;
				while(i<=cur){
					leftmost_min[(x[i]-'0')]=min(leftmost_min[(x[i]-'0')],i);
					++i;
				}
				--i;
			}
		}
	}
	return x;
}

void run_case(){
	string s;
	cin >> s;
	//cout<<run_filter(s,1)<<endl;
	string ans1,ans2;
	time__("MAIN"){
		ans1 = run_filter(run_filter(s,1),0);
		//cout<<ans1<<endl;
		ans2 = run_filter(run_filter(s,0),1);
	}
	//cout<<ans2<<endl;
	if(ans1<ans2)
		cout << ans1;
	cout << ans2;
	cout<<"\n";
}
int main(){
	fast;	
	#ifndef ONLINE_JUDGE 
  
    // For getting input from input.txt file 
    freopen("example.txt", "r", stdin); 
  
    // Printing the Output to output.txt file 
    freopen("output.txt", "w", stdout); 
  
#endif 
	int t;
	cin >> t;
	while(t--){
		run_case();
	}	
}