#include <iostream>
using namespace std;

int main() {
  int T;
  cin>>T;
  while(T--){
  string s;
  cin>>s;
for(int p=1;p<=s.length();p++){
int x=p;
int cnt=0;
while(x){
    cnt+=(x&1);
    x>>=1;
}
if(cnt%2!=0){
s[p-1]=toupper(s[p-1]);
}

}
cout<<s<<endl;
 }

return 0;
}