#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll m;
int gt(int n)
{
int res=1;
for(int i=0;i<n;i++)
{
res*=2;
}
return res;
}
string he10sang2()
{
string str="";
while(m!=0)
{
str+=char(m%2 + 48);
m/=2;
}
//cout<<str<<endl;
reverse(str.begin(),str.end());
return str;
}
main()
{
int t;cin>>t;
while(t--)
{
cin>>m;
string str=he10sang2();
//cout<<str<<endl;
int n=str.size();
int mod=n%4;
if(mod>0) str=string(4-mod,'0') + str;
reverse(str.begin(),str.end());
string kq="";
for(int i=0;i<n;i+=4)
{
int res=0;
for(int j=i;j<i+4;j++)
{
if(str[j]=='1')
{
res+=gt(j-i);
}
}
if(res<10) kq= char(res+48) + kq;
else kq= char(res%10 + 65) + kq;
}
cout<<kq<<endl;
}
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBsbCBsb25nIGxvbmcKbGwgbTsKaW50IGd0KGludCBuKQp7ICAgCiAgICBpbnQgcmVzPTE7Cglmb3IoaW50IGk9MDtpPG47aSsrKQoJewoJCXJlcyo9MjsKCX0KCXJldHVybiByZXM7Cn0Kc3RyaW5nIGhlMTBzYW5nMigpCnsKCXN0cmluZyBzdHI9IiI7Cgl3aGlsZShtIT0wKQoJewoJCXN0cis9Y2hhcihtJTIgKyA0OCk7CgkJbS89MjsKCX0KCS8vY291dDw8c3RyPDxlbmRsOwoJcmV2ZXJzZShzdHIuYmVnaW4oKSxzdHIuZW5kKCkpOwoJcmV0dXJuIHN0cjsKfQptYWluKCkKewoJaW50IHQ7Y2luPj50OwoJd2hpbGUodC0tKQoJewoJCWNpbj4+bTsKCQlzdHJpbmcgc3RyPWhlMTBzYW5nMigpOwoJCS8vY291dDw8c3RyPDxlbmRsOwoJCWludCBuPXN0ci5zaXplKCk7CgkJaW50IG1vZD1uJTQ7CgkJaWYobW9kPjApIHN0cj1zdHJpbmcoNC1tb2QsJzAnKSArIHN0cjsgCgkJcmV2ZXJzZShzdHIuYmVnaW4oKSxzdHIuZW5kKCkpOwoJCXN0cmluZyBrcT0iIjsKCQkKCQlmb3IoaW50IGk9MDtpPG47aSs9NCkKCQl7CgkJCWludCByZXM9MDsKCQkJZm9yKGludCBqPWk7ajxpKzQ7aisrKQoJCQl7CgkJCQlpZihzdHJbal09PScxJykKCQkJCXsKCQkJCQkKCQkJCQlyZXMrPWd0KGotaSk7CgkJCQl9CgkJCX0KCQkJaWYocmVzPDEwKSBrcT0gY2hhcihyZXMrNDgpICsga3E7CgkJCWVsc2Uga3E9IGNoYXIocmVzJTEwICsgNjUpICsga3E7IAoJCX0KCQljb3V0PDxrcTw8ZW5kbDsKCX0KfQ==