#include<iostream>
#include<string>
#include <algorithm>
#include <locale>
using namespace std;
int main(){
string a;
int t;
cin>>t;
for(int i=0;i<t;i++)
{cin>> a;
char f,s;
f=a[0] ;
string b=a;
int min=0;
sort(b.begin(),b.end());
string str=a;
sort(str.begin(),str.end());
for(int k=0;k<b.size();k++)
{if(f!=b[k] && str[k]!=a[k])
{min=k ; f=a[k]; for(int ss=min;ss<b.size();ss++)if(f!=b[ss]){min=ss; break;}
break;
}
}
b=b.substr(min);
/*for(int k=0;k<b.size();k++)
{if(b[k]==f)
b=b.substr(1);
}*/
//sort(b.begin(),b.end());
s=b[0];
for(int k=0;k<b.size();k++)
{if(min!=0)
if(a[min-1]!=b[k] )
{s=b[k]; break;}
}
for(int k=0;k<a.size();k++)
{if(f>s )
{ break;
}else
if(f<s)
f=a[k];
}
//cout<<b<<endl<<"F=" <<f<<" S="<<s<<endl;
//continue;
//s=b[0];
/*for(int j=0;j<a.size();j++)
{if(f==s)
s=a[j];
if(f!=s)
break;}
*/
//a[0]=s;
for(int i=0;i<a.size();i++)
{if(a[i]==f)
{a[i]=s; continue;}
if(a[i]==s)
a[i]=f;
}
cout<<a<<endl;
}
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHN0cmluZz4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGxvY2FsZT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IG1haW4oKXsKCXN0cmluZyBhOwoJaW50IHQ7CgljaW4+PnQ7Cglmb3IoaW50IGk9MDtpPHQ7aSsrKQoJe2Npbj4+IGE7CgljaGFyIGYsczsKCWY9YVswXSA7CglzdHJpbmcgYj1hOwoJCglpbnQgbWluPTA7Cglzb3J0KGIuYmVnaW4oKSxiLmVuZCgpKTsKCXN0cmluZyBzdHI9YTsKCQlzb3J0KHN0ci5iZWdpbigpLHN0ci5lbmQoKSk7CgoJZm9yKGludCBrPTA7azxiLnNpemUoKTtrKyspCgl7aWYoZiE9YltrXSAmJiBzdHJba10hPWFba10pCgl7bWluPWsgOyBmPWFba107IGZvcihpbnQgc3M9bWluO3NzPGIuc2l6ZSgpO3NzKyspaWYoZiE9Yltzc10pe21pbj1zczsgYnJlYWs7fQoJYnJlYWs7Cgl9Cgl9CgkKCWI9Yi5zdWJzdHIobWluKTsKCS8qZm9yKGludCBrPTA7azxiLnNpemUoKTtrKyspCgl7aWYoYltrXT09ZikKCSAgYj1iLnN1YnN0cigxKTsKCX0qLwoJCS8vc29ydChiLmJlZ2luKCksYi5lbmQoKSk7CglzPWJbMF07Cglmb3IoaW50IGs9MDtrPGIuc2l6ZSgpO2srKykKCXtpZihtaW4hPTApCgkJaWYoYVttaW4tMV0hPWJba10gKQoJe3M9YltrXTsgYnJlYWs7fQoJCgl9CgkKCWZvcihpbnQgaz0wO2s8YS5zaXplKCk7aysrKQoJe2lmKGY+cyApCgl7IGJyZWFrOwoJfWVsc2UKCWlmKGY8cykKCQlmPWFba107CgoJfQoJCgkvL2NvdXQ8PGI8PGVuZGw8PCJGPSIgPDxmPDwiIFM9Ijw8czw8ZW5kbDsKCS8vY29udGludWU7CgoJCgkvL3M9YlswXTsKCS8qZm9yKGludCBqPTA7ajxhLnNpemUoKTtqKyspCgl7aWYoZj09cykKCQlzPWFbal07CglpZihmIT1zKQoJCWJyZWFrO30KCSovCgkvL2FbMF09czsKCQoJZm9yKGludCBpPTA7aTxhLnNpemUoKTtpKyspCgl7aWYoYVtpXT09ZikKCXthW2ldPXM7IGNvbnRpbnVlO30KCWlmKGFbaV09PXMpCgkJYVtpXT1mOwoJCgoJfQoKCgljb3V0PDxhPDxlbmRsOwoKCX0KCnJldHVybiAwOwp9