#include <bits/stdc++.h>
using namespace std;

int main() {
    map<char, string> h = {
        {'0', "0000"}, {'1', "0001"}, {'2', "0010"}, {'3', "0011"},
        {'4', "0100"}, {'5', "0101"}, {'6', "0110"}, {'7', "0111"},
        {'8', "1000"}, {'9', "1001"}, {'A', "1010"}, {'B', "1011"},
        {'C', "1100"}, {'D', "1101"}, {'E', "1110"}, {'F', "1111"}
    };
    
    map<string, char> b = {
        {"000", '0'}, {"001", '1'}, {"010", '2'}, {"011", '3'},
        {"100", '4'}, {"101", '5'}, {"110", '6'}, {"111", '7'}
    };

    int n;
    cin >> n;
    while (n--) {
        string hex, bin, oct;
        cin >> hex;
        for (char c : hex) {
            bin += h[toupper(c)];
        }
        int len = bin.length();
        if (len % 3 == 1) bin = "00" + bin;
        else if (len % 3 == 2) bin = "0" + bin;
        bool flag = false;
        for (int i = 0; i < bin.length(); i += 3) {
            string g = bin.substr(i, 3);
            char o = b[g];
            if (!flag && o != '0') flag = true;
            if (flag) oct += o;
        }
        
        cout << (oct.empty() ? "0" : oct) << endl;
    }
    return 0;
}