#include <bits/stdc++.h>
using namespace std;
class Node {
 public:
  Node *prev, *next;
  int k;
  Node(int K) {
    k = K;
    prev = next = NULL;
  };
  void insert(int K) {
    Node *n = new Node(K);
    n->prev = this;
    if (this->next == NULL)
      this->next = n;
    else {
      Node *t = this->next;
      this->next = n;
      n->next = t;
      t->prev = n;
    }
  };
  void insertBack(int K) {
    Node *n = new Node(K);
    n->next = this;
    if (this->prev == NULL)
      this->prev = n;
    else {
      Node *t = this->prev;
      this->prev = n;
      n->prev = t;
      t->next = n;
    }
  };
  void del() {
    Node *p = this->prev, *n = this->next;
    if (p) p->next = n;
    if (n) n->prev = p;
    delete this;
  };
  void delNext() {
    if (this->next) this->next->del();
  };
};
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int T;
  cin >> T;
  while (T) {
    T--;
    string s;
    cin >> s;
    Node *head = new Node(s[0] - '0');
    Node *curr = head;
    for (int i = 1; i < s.size(); i++) {
      curr->insert(s[i] - '0');
      curr = curr->next;
    }
    curr = head->next;
    Node *cache = head;
    while (curr) {
      if (cache->k % 2 != curr->k % 2) {
        while (cache->k < curr->k) cache = cache->next;
        if (cache == curr) {
          curr = curr->next;
          continue;
        }
        cache->insertBack(curr->k);
        if (curr->next) {
          curr = curr->next;
          curr->prev->del();
        } else {
          curr = curr->prev;
          curr->next->del();
          curr = NULL;
        }
      } else {
        curr = curr->next;
      }
    }
    while (cache->prev) cache = cache->prev;
    while (cache) {
      cout << cache->k;
      cache = cache->next;
      if (cache && cache->prev) cache->prev->del();
    }
    cout << endl;
  }
  return 0;
}
