#include <iostream>
#include <cstring>
using namespace std;
int main()
{
int t;
cin>>t;
ios::sync_with_stdio(false);
while(t--)
{
char kolejka[1000000] = {0};
cin>> kolejka;
int rozmiar = strlen(kolejka);
int maks = kolejka[rozmiar-1];
for(int i = rozmiar - 1; i > 0; i-- )
{
if(kolejka[i-1] < maks)
kolejka[i-1] = '*'; //tylko dla pokazania Ci błędu, zamiast 0
else if ( kolejka[i-1] > maks)
maks = kolejka[i-1];
}
for(int x=0; x < rozmiar; x++)
cout<<kolejka[x];
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0cmluZz4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtYWluKCkKewogICAgICAgIGludCB0OwogICAgICAgIGNpbj4+dDsKICAgICAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CgoKICAgIHdoaWxlKHQtLSkKICAgIHsKICAgICAgICBjaGFyIGtvbGVqa2FbMTAwMDAwMF0gPSB7MH07CiAgICAgICAgY2luPj4ga29sZWprYTsKICAgICAgICBpbnQgcm96bWlhciA9IHN0cmxlbihrb2xlamthKTsKICAgICAgICBpbnQgbWFrcyA9IGtvbGVqa2Fbcm96bWlhci0xXTsKICAgICAgICAKICAgICAgICBmb3IoaW50IGkgPSByb3ptaWFyIC0gMTsgaSA+IDA7IGktLSApCiAgICAgICAgewogICAgICAgICAgICBpZihrb2xlamthW2ktMV0gPCBtYWtzKQogICAgICAgICAgICAgICAga29sZWprYVtpLTFdID0gJyonOyAvL3R5bGtvIGRsYSBwb2themFuaWEgQ2kgYsWCxJlkdSwgemFtaWFzdCAwIAoKICAgICAgICBlbHNlIGlmICgga29sZWprYVtpLTFdID4gbWFrcykKICAgICAgICAgICAgICAgIG1ha3MgPSBrb2xlamthW2ktMV07CiAgICAgICAgfQogICAgICAgICBmb3IoaW50IHg9MDsgeCA8IHJvem1pYXI7IHgrKykKICAgICAgICAgICAgICAgIGNvdXQ8PGtvbGVqa2FbeF07CgogICAgfQoKCiAgICByZXR1cm4gMDsKfQ==