#include <bits/stdc++.h>
using namespace std;
void solveFunction() {
  string s;
  cin >> s;
  vector<int> v[10];
  set<int> used;
  for (int i = s.length() - 1; i >= 0; i--) {
    v[s[i] - '0'].push_back(i);
  }
  int i = 0;
  string ans = "";
  while (i < s.length()) {
    if (used.find(i) != used.end()) {
      i++;
      continue;
    }
    int p = (s[i] - '0') % 2;
    p ^= 1;
    int x = s[i] - '0';
    int mn = INT_MAX;
    int mn1 = INT_MAX;
    for (int j = p; j < 10; j += 2) {
      if (j < x) {
        if (v[j].size()) mn = min(mn, v[j].back());
      } else {
        if (v[j].size()) mn1 = min(mn1, v[j].back());
      }
    }
    if (mn == INT_MAX || mn > mn1) {
      ans += s[i];
      v[s[i] - '0'].pop_back();
      used.insert(i);
      i++;
    } else {
      ans += s[mn];
      used.insert(mn);
      v[s[mn] - '0'].pop_back();
    }
  }
  cout << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  int t = 1;
  cin >> t;
  while (t--) {
    solveFunction();
  }
}
