#include <bits/stdc++.h>
using namespace std;
char s[100005];
string ss;
map<string,int> mk;
int ok[600005];
void trans(int x)
{
    if(s[x]=='0') ss+="0000";
    else if(s[x]=='1') ss+="0001";
    else if(s[x]=='2') ss+="0010";
    else if(s[x]=='3') ss+="0011";
    else if(s[x]=='4') ss+="0100";
    else if(s[x]=='5') ss+="0101";
    else if(s[x]=='6') ss+="0110";
    else if(s[x]=='7') ss+="0111";
    else if(s[x]=='8') ss+="1000";
    else if(s[x]=='9') ss+="1001";
    else if(s[x]=='A') ss+="1010";
    else if(s[x]=='B') ss+="1011";
    else if(s[x]=='C') ss+="1100";
    else if(s[x]=='D') ss+="1101";
    else if(s[x]=='E') ss+="1110";
    else ss+="1111";
}
int go(int x)
{
    string re="";
    re.push_back(ss[x]);
    re.push_back(ss[x+1]);
    re.push_back(ss[x+2]);
    return mk[re];
}
void solve()
{
    ss="";
    int p=0;
    scanf("%s",s+1);
    int len=strlen(s+1);
    for(int i=1;i<=len;i++) trans(i);
    int now=3-(ss.size()%3);
    for(int i=1;i<=now;i++) ss="0"+ss;
    for(int i=0;i<ss.size();i+=3) ok[++p]=go(i);
    int pos=p+1;
    for(int i=1;i<=p;i++) if(ok[i])
    {
        pos=i;
        break;
    }
    if(pos==p+1) puts("0");
    else 
    {
        for(int i=pos;i<=p;i++) printf("%d",ok[i]);
        printf("\n"); 
    }
}
int main()
{
    mk["000"]=0;mk["001"]=1;mk["010"]=2;mk["011"]=3;mk["100"]=4;mk["101"]=5;mk["110"]=6;mk["111"]=7;
    int t;
    scanf("%d",&t);
    while(t--) solve();
}