#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#define FOR(i,x,n) for(int i=x;i<n;i++)
#define ll long long int
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define MAX_N 50005

using namespace std;

map<char,string > ma1;
map<string,char > ma2;
char a[100005];
int two[400005];
char eight[200000];
int couEight=0;

void sett(){
    ma1[‘0‘]="0000";
    ma1[‘1‘]="0001";
    ma1[‘2‘]="0010";
    ma1[‘3‘]="0011";
    ma1[‘4‘]="0100";
    ma1[‘5‘]="0101";
    ma1[‘6‘]="0110";
    ma1[‘7‘]="0111";
    ma1[‘8‘]="1000";
    ma1[‘9‘]="1001";
    ma1[‘A‘]="1010";
    ma1[‘B‘]="1011";
    ma1[‘C‘]="1100";
    ma1[‘D‘]="1101";
    ma1[‘E‘]="1110";
    ma1[‘F‘]="1111";

    ma2["000"]=‘0‘;
    ma2["001"]=‘1‘;
    ma2["010"]=‘2‘;
    ma2["011"]=‘3‘;
    ma2["100"]=‘4‘;
    ma2["101"]=‘5‘;
    ma2["110"]=‘6‘;
    ma2["111"]=‘7‘;
}

int main()
{
    //freopen("input1.txt", "r", stdin);
    //freopen("data.out", "w", stdout);
    int N;
    sett();
    scanf("%d",&N);
    getchar();
    while(N--){
        scanf("%s",a);
        getchar();
        int cou=0;
        couEight=0;
        FOR(i,0,strlen(a)){
            string t1=ma1[a[i]];
            two[cou++]=t1[0]-‘0‘;
            two[cou++]=t1[1]-‘0‘;
            two[cou++]=t1[2]-‘0‘;
            two[cou++]=t1[3]-‘0‘;
        }
        int tt=cou%3;
        if(tt==0){
            couEight=0;
            for(int i=0;i<cou;i+=3){
                string t2="";
                t2+=two[i]+‘0‘;
                t2+=two[i+1]+‘0‘;
                t2+=two[i+2]+‘0‘;
                if(ma2[t2]==‘0‘){
                    if(i>0){
                        printf("%c",ma2[t2]);
                    }
                }else{
                    printf("%c",ma2[t2]);
                }
            }
            printf("\n");
        }else if(tt==1){
            couEight=0;
            if(two[0]==1){
                printf("1");
            }
            for(int i=1;i<cou;i+=3){
                string t3="";
                t3+=two[i]+‘0‘;
                t3+=two[i+1]+‘0‘;
                t3+=two[i+2]+‘0‘;
                if(ma2[t3]==‘0‘){
                    if(i>1){
                        printf("%c",ma2[t3]);
                    }
                }else{
                    printf("%c",ma2[t3]);
                }
            }
            printf("\n");
        }else if(tt==2){
            couEight=0;
            string t0="";
            t0+=‘0‘;
            t0+=two[0]+‘0‘;
            t0+=two[1]+‘0‘;
            if(ma2[t0]!=‘0‘){
                printf("%c",ma2[t0]);
            }

            for(int i=2;i<cou;i+=3){
                string t4="";
                t4+=two[i]+‘0‘;
                t4+=two[i+1]+‘0‘;
                t4+=two[i+2]+‘0‘;
                if(ma2[t4]==‘0‘){
                    if(i>2){
                        printf("%c",ma2[t4]);
                    }
                }else{
                    printf("%c",ma2[t4]);
                }
            }
            printf("\n");
        }

    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}