#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;

deque<int> adj[500];

struct fenwick{
    vector<int> ft;
    int n;
    fenwick(int _n){
        n = _n + 5;
        ft.assign(n, 0);
    }
    void update(int pos, int x){
        for(int i = pos; i < n; i+=(i&(-i)))
            ft[i] += x;
    }
    int query(int pos){
        int sum = 0;
        for(int i = pos; i > 0; i-=(i&(-i)))
            sum += ft[i];
        return sum;
    }
    int query(int esq, int dir){
        return query(dir) - query(esq - 1);
    }
};

int main(){

    cout.sync_with_stdio(0);
    cin.tie(0);

    int t; cin >> t;
    while(t--){
        string s; cin >> s;
        s = "$" + s;
        int n = s.size();
        for(int i = 1; i < n; i++)
            adj[s[i]].emplace_back(i);
        fenwick ft(n+5);

        for(int i = 'a'; i <= 'z'; i++)
            if(adj[i].size())
                ft.update(adj[i].back(), +1);

        string res;
        for(int i = 1; i < n; i++){
            int flag = -1;
            char c = s[i];
            if(adj[c].empty()) continue;
            for(int j = 'z'; j > c; j--)
                if(adj[j].size()){
                    int dir = adj[j].front();
                    int esq = i;
                    if(ft.query(esq, dir-1) == 0){
                        flag = j;
                        break;
                    }
                }
            // cout << i << " " << flag << endl;
            if(flag == -1){
                res += s[i];
                ft.update(adj[c].back(), -1);
                adj[c].clear();
            }
            else{
                for(int j = 'a'; j <= 'z'; j++)
                    while(!adj[j].empty() && adj[j].front() < adj[flag].front())
                        adj[j].pop_front();
                i = adj[flag].front() - 1;
            }
        }
        cout << res << endl;
    }

    return 0;
}