#include <bits/stdc++.h>
using namespace std;
 
void swap_chars(string &s, int i, int j) {
    char temp = s[i];
    s[i] = s[j];
    s[j] = temp;
}
 
int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        int pos;
        for (int i = 0; i < s.size(); i++) {
        	int k=0;pos=i;
        	for(int j=i;j<min(i+10,(int)s.size());j++)
        	{ if (s[j] - s[i] > j-i+k) {
                k=s[j]-s[i]-j+i;pos=j; }
        }while(pos>i){swap_chars(s,pos,pos-1);s[pos-1]--;pos--;}
      }
        cout << s << endl;
    }
    return 0;
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp2b2lkIHN3YXBfY2hhcnMoc3RyaW5nICZzLCBpbnQgaSwgaW50IGopIHsKICAgIGNoYXIgdGVtcCA9IHNbaV07CiAgICBzW2ldID0gc1tqXTsKICAgIHNbal0gPSB0ZW1wOwp9CgppbnQgbWFpbigpIHsKICAgIGludCB0OwogICAgY2luID4+IHQ7CiAgICB3aGlsZSAodC0tKSB7CiAgICAgICAgc3RyaW5nIHM7CiAgICAgICAgY2luID4+IHM7CiAgICAgICAgaW50IHBvczsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IHMuc2l6ZSgpOyBpKyspIHsKICAgICAgICAJaW50IGs9MDtwb3M9aTsKICAgICAgICAJZm9yKGludCBqPWk7ajxtaW4oaSsxMCwoaW50KXMuc2l6ZSgpKTtqKyspCiAgICAgICAgCXsgaWYgKHNbal0gLSBzW2ldID4gai1pK2spIHsKICAgICAgICAgICAgICAgIGs9c1tqXS1zW2ldLWoraTtwb3M9ajsgfQogICAgICAgIH13aGlsZShwb3M+aSl7c3dhcF9jaGFycyhzLHBvcyxwb3MtMSk7c1twb3MtMV0tLTtwb3MtLTt9CiAgICAgIH0KICAgICAgICBjb3V0IDw8IHMgPDwgZW5kbDsKICAgIH0KICAgIHJldHVybiAwOwp9Cg==

NgoxOQoxNzA5CjExNTU1CjUxNDc2Cjk4NzY1NDMyMTAKNTg5MTkxNzg5OQo=

6
19
1709
11555
51476
9876543210
5891917899