//大佬没事看看我这个第二题，，，先看的第三题，写了一下，没过，剩下时间都在写第二题，
//想着不急，打了个表，但是0通过。。。。。。。


/*************************************************************************     > File Name: 2.cpp     > Author:      > Mail:      > Created Time: 2019年04月06日 星期六 20时00分57秒
 ************************************************************************/

#include<iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <map>
using namespace std;

void diyi(string &str) {
    int k = str.size() % 3;
    if (k == 2) str = "0" + str;
    else if (k == 1) str = "00" + str;
}


void dier(string &str) {
    string tt;
    map<char,string> ma;
    ma['0'] = "0000";
    ma['1'] = "0001";
    ma['2'] = "0010";
    ma['3'] = "0011";
    ma['4'] = "0100";
    ma['5'] = "0101";
    ma['6'] = "0110";
    ma['7'] = "0111";
    ma['8'] = "1000";
    ma['9'] = "1001";
    ma['a'] = "1010";
    ma['b'] = "1011";
    ma['c'] = "1100";
    ma['d'] = "1101";
    ma['e'] = "1110";
    ma['f'] = "1111";
    //cout << str << endl;
    for (int i = 0; i < str.size(); i+= 3) {
        string te;
        int k = 0;
        int temp = 0;
        char ch[32];
        for (int kk = 0; kk < 32; kk++) ch[kk] = 0;
        while (k < 3) {
            temp = temp * 10 + str[i + k] - '0';
            k++;
        }
        //55 37
        sprintf(ch,"%0x",temp);
        int j = 0;
        while (ch[j]) {
            te += ma[ch[j]];
            j++;
        }
        j = 0;
        while (j < te.size() && te[j] == '0') {
            te.erase(j,j + 1);
        }
        tt += te;
    }
    str = tt;
    return ;
}
void disan(string &str) {
    int k = str.size() % 5;
    if (k == 1) str = "0000" + str;
    else if (k == 2) str = "000" + str;
    else if (k == 3) str = "00" + str;
    else if (k == 4) str = "0" + str;

}

void disi(string &str) {
    string te;
    map<string,string> ma;
    ma["00000"] = "0";
    ma["00001"] = "1";
    ma["00010"] = "2";
    ma["00011"] = "3";
    ma["00100"] = "4";
    ma["00101"] = "5";
    ma["00110"] = "6";
    ma["00111"] = "7";
    ma["01000"] = "8";
    ma["01001"] = "9";
    ma["01010"] = "A";
    ma["01011"] = "B";
    ma["01100"] = "C";
    ma["01101"] = "D";
    ma["01110"] = "E";
    ma["01111"] = "F";
    ma["10000"] = "G";
    ma["10001"] = "H";
    ma["10010"] = "I";
    ma["10011"] = "J";
    ma["10100"] = "K";
    ma["10101"] = "L";
    ma["10110"] = "M";
    ma["10111"] = "N";
    ma["11000"] = "O";
    ma["11001"] = "P";
    ma["11010"] = "Q";
    ma["11011"] = "R";
    ma["11100"] = "S";
    ma["11101"] = "T";
    ma["11110"] = "U";
    ma["11111"] = "V";
    for (int i = 0; i < str.size(); i+= 5) {
        int k = 0;
        string tt;
        while (k < 5) {
            tt += str[i + k];
            k++;
        }
        te += ma[tt];
        //cout << "tt "<< tt << endl;
    }
    str = te;
    return ;
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        string str;
        cin >> str;
        diyi(str);
        dier(str);
        disan(str);
        disi(str);
        cout << str << endl;
    }
    return 0;
}