#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int N = 200 * 1000 + 13;

int n;
int cnt[10];
string s, t;
int pr0[N];

bool check(int pos){
    int c = accumulate(cnt, cnt + 10, 0);

    if (c > n - pos)
        return false;
    if (pr0[n - c] - pr0[pos] > 0)
        return true;

    int nxt = 0;

    for (int i = n - c; i < n; ++i, ++nxt){
        while (cnt[nxt] == 0) ++nxt;

        if (s[i] > '0' + nxt)
            return true;
        if (s[i] < '0' + nxt)
            return false;
    }

    return false;
}

bool can(int pos){
    int c = accumulate(cnt, cnt + 10, 0);
    return (c <= n - pos);
}

void fix(int pos){
    int c = accumulate(cnt, cnt + 10, 0);

    t += string(n - pos - c, '9');

    int nxt = 9;
    while (nxt >= 0){
        while (nxt >= 0 && cnt[nxt] == 0) --nxt;
        if (nxt >= 0){
            t += '0' + nxt;
            --nxt;
        }
    }
}

char buf[N];

bool read(){
    if (scanf("%s", buf) != 1)
        return false;

    s = buf;
    n = s.size();

    return true;
}

void solve(){
    t = "";

    pr0[0] = 0;
    forn(i, n)
        pr0[i + 1] = pr0[i] + (s[i] > '0');

    if (s[0] == '1' && pr0[n] == 1){
        printf("%s\n", string(n - 2, '9').c_str());
        return;
    }

    if (s[0] == '1' && s[n - 1] == '1' && pr0[n] == 2){
        printf("%s\n", string(n - 2, '9').c_str());
        return;
    }

    memset(cnt, 0, sizeof(cnt));
    forn(i, n){
        if (i < n - 1){
            cnt[s[i] - '0'] ^= 1;
            if (check(i + 1)){
                t += s[i];
                continue;
            }
            cnt[s[i] - '0'] ^= 1;
        }

        for (char c = s[i] - 1; c >= '0'; --c){
            cnt[c - '0'] ^= 1;
            if (can(i + 1)){
                t += c;
                fix(i + 1);
                break;
            }
            cnt[c - '0'] ^= 1;
        }

        break;
    }

    printf("%s\n", t.c_str());
}

int main(){
    int tc;
    scanf("%d", &tc);
    while (tc--){
        read();
        solve();
    }
    return 0;
}