import java.util.Scanner;
import java.util.Vector;

public class Main {

    static public void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        in.nextLine();
        while (n-- > 0) {
            // 第一次 补齐0
            String string = in.nextLine();
            if (string.length() % 3 == 1) {
                string = "00" + string;
            } else if (string.length() % 3 == 2) {
                string = "0" + string;
            }
            // 将十进制转换成2进制
            Vector<String> vector = new Vector<>();
            int threeNum = string.length() / 3;
            String tenStr = "";
            for (int i = 0; i < threeNum; i++) {
                String temp = string.substring(i * 3, i * 3 + 3);
                temp = Integer.toString(Integer.parseInt(temp), 2);
                int tempLen = temp.length();
                for (int j = 0; j < 10 - tempLen; j++) {
                    temp = "0" + temp;
                }
                tenStr = tenStr + temp;
            }
            // 去掉前导零
            int tenStrLen = tenStr.length();
            String tempStr = tenStr;
            for (int i = 0; i < tenStrLen; i++) {
                if (tenStr.charAt(i) == '0') {
                    tempStr = tenStr.substring(i + 1, tenStrLen);
                } else {

                    break;
                }
            }
            tenStr = tempStr;
            tenStrLen = tenStr.length();
            for (int i = 0; i < tenStrLen; i++) {
                if (tenStr.charAt(i) == '0') {
                    tempStr = tenStr.substring(i + 1, tenStrLen);
                } else {

                    break;
                }
            }
            tenStrLen = tenStr.length();
            int howManyFive = tenStr.length() % 5;
            if (howManyFive != 0) {
                while (howManyFive++ < 5) {
                    tenStr = "0" + tenStr;
                }
            }
            String result = "";
            tenStrLen = tenStr.length();
            int fiveTime = tenStrLen / 5;

            while (fiveTime-- > 0) {

                result = Integer.toString(Integer.parseInt(tenStr.substring(5 * fiveTime, 5 * fiveTime + 5), 2), 32)
                        + result;

            }
            System.out.println(result.toUpperCase());
        }
    }

}