#include <bits/stdc++.h>
using namespace std;
deque<int> dq[300005], ans;
int ara[300005];
char str[300005];
int main() {
  int ts, n;
  scanf("%d", &ts);
  while (ts--) {
    scanf("%s", str);
    n = strlen(str);
    for (int i = 0; i < n; i++) ara[i] = (str[i] - '0');
    int m = 0;
    for (int i = 0; i < n; i++) {
      bool f = (ara[i] & 1);
      while (i < n && (ara[i] & 1) == f) dq[m].push_back(ara[i]), i++;
      i--;
      m++;
    }
    for (int i = 1; i <= m; i++) {
      while (!dq[0].empty() && !dq[i].empty()) {
        if (dq[0].front() < dq[i].front())
          ans.push_back(dq[0].front()), dq[0].pop_front();
        else
          ans.push_back(dq[i].front()), dq[i].pop_front();
      }
      if (dq[0].empty()) {
        while (!dq[i].empty())
          dq[0].push_back(dq[i].front()), dq[i].pop_front();
      } else {
        while (!dq[i + 1].empty())
          dq[0].push_back(dq[i + 1].front()), dq[i + 1].pop_front();
        i++;
      }
    }
    if (!dq[0].empty()) {
      while (!dq[0].empty()) ans.push_back(dq[0].front()), dq[0].pop_front();
    }
    while (!ans.empty()) printf("%d", ans.front()), ans.pop_front();
    puts("");
  }
  return 0;
}
