#include<bits/stdc++.h>
using namespace std;
int t, n, s, l, i, j;
string a;
signed main() {
	cin >> t;
	while (t --) {
		cin >> a;
		l = a.size();
		for (i = 0; i < l; i ++) {
			n = a[i] - '0', s = i;
			for (j = 0; j < 9 && i + j <= l; j ++)
				if (n < a[i + j] - '0' - j)
					n = a[i + j] - '0' - j, s = i + j;
			if (s == i)
				continue;
			for (j = s; j > i; j --)
				swap(a[j - 1], a[j - 2]);
			a[i] = n + '0';
		}
		cout << a << endl;
	}
}