#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;   }   