#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define len(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<vector<int>>
#define vpii vector<pair<int, int>>
#define ull unsigned long long
//#define int long long
const int N = 2e5 + 5;
const int C = 20;
const int logn = 20;
const ll inf = 1e12;
const int mod = 1e9 + 7;
const int M = 1e9;
const ull M2 = 998244353;
const ld eps = 1e-6;
using namespace std;

template<class T>
istream &operator>>(istream &in, vector<T> &a) {
    for (auto &i : a)
        in >> i;
    return in;
}

template<class T>
ostream &operator<<(ostream &out, vector<T> &a) {
    for (auto &i : a)
        out << i;
    return out;
}

ld f(ld x0, vector<ld>& x, vector<ld>& t) {
    ld ans = 1e17 + 1.0;
    for (int i = 0; i < len(x); ++i) {
        ans = min(ans, t[i] + abs(x[i] - x0));
    }
    return ans;
}

void solve() {
    string s; cin >> s;
    int n = len(s);
    vector<int> d1, d2;
    int i = -1;
    while (i + 1 < n) {
        int mini = i + 1;
        for (int j = i + 1; j < n; ++j)
            if ((s[j] - '0') < (s[mini] - '0'))
                mini = j;
        d1.push_back(s[mini] - '0');
        for (int j = i + 1; j < mini; ++j)
            d2.push_back(min(s[j] - '0' + 1, 9));
        i = mini;
    }
    for (auto c : d2)
        d1.push_back(c);
    sort(all(d1));
    cout << d1;
    cout << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int T = 1;
    cin >> T;
    while (T--)
        solve();
}

/*
     ▄▀▀▀▄
▄███▀░◐░░░▌
    ▌░░░░░▐
    ▐░░░░░▐
    ▌░░░░░▐▄▄
    ▌░░░░▄▀▒▒▀▀▀▀▄
   ▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
   ▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
    ▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
      ▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
           ▌▌░▌▌
           ▌▌░▌▌
         ▄▄▌▌▄▌▌        */