#include <bits/stdc++.h>

#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef ld typ;
typedef string str;

struct point
{
    ld x, y;
};

struct vec
{
    ld a, b;
};

struct line
{
    ld a, b, c;
};

istream& operator>> ( istream& in, point& p)
{
   in >> p.x >> p.y;
   return in;
}

ostream& operator<<(ostream& out, point& p)
{
    out << p.x << ' ' << p.y;
    return out;
}

void build(ll, ll, ll);
ll _max(ll, ll, ll, ll, ll);
void update(ll, ll, ll, ll, ll, ll);
typ sqr(typ);
void start();
void extended(int);
point n_point(point, point);
vec mv(point, point);
line ml(point, point);
typ croos(vec, vec);
typ skalar(vec, vec);

int a[100000], d[400000], updateb[400000];

ll check(str s)
{
    ll sum = 0, p = 1;
    for (int i = s.size() - 1; i >= 0; i--)
    {
        if (s[i] == '1')
            sum  += p;
        p *= 2;
    }
    return sum;
}

char out(ll s)
{
    if (s <= 9)
        return (char)(s + '0');
    if (s == 10)
        return 'A';
    if (s == 11)
        return 'B';
    if (s == 12)
        return 'C';
    if (s == 13)
        return 'D';
    if (s == 14)
        return 'R';
    if (s == 15)
        return 'F';
}

int main()
{
    start();
    ll n;
    cin >> n;
    for (int j = 0; j < n; j++)
    {
        str s, a;
        cin >> s;
        if (s.size() % 4)
            a = s.substr(0, s.size() % 4);
        cout << out(check(a));
        for (int i = s.size() % 4; i < s.size(); i+= 4)
        {
            a = s.substr(i, 4);
            cout << out(check(a));
        }
        cout << endl;
    }
    return 0;
}

void build(ll v, ll tl, ll tr)
{
    if (tl == tr)
        d[v] = a[tl];
    else
    {
        ll tm = (tl + tr) / 2;
        build(v * 2, tl, tm);
        build(v * 2 + 1, tm + 1, tr);
        d[v] = max(d[v * 2], d[v * 2 + 1]);
    }
}

ll _max(ll v, ll tl, ll tr, ll l, ll r)
{
    if (l > r)
        return 0;
    if (tl == l && tr == r)
        return d[v] + updateb[v];
    ll tm = (tl + tr) / 2;
    return max(_max(v * 2, tl, tm, l, min(r, tm)), _max(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r)) + updateb[v];
}

void update(ll v, ll tl, ll tr, ll l, ll r, ll s)
{
    if (l > r)
        return;
    if (tl == l && tr == r)
    {
        updateb[v] += s;
        return;
    }
    ll tm = (tl + tr) / 2;
    update(v * 2, tl, tm, l, min(r, tm), s);
    update(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r, s);
}

ld sqr(ld a)
{
    return a * a;
}

void start()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

void extended(int n)
{
    cout << setprecision(n) << fixed;
}

point n_point(point a, point b)
{
    point n;
    n.x = a.x;
    n.y = b.y;
    return n;
}

vec mv(point st, point fn)
{
    vec v;
    v.a = fn.x - st.x;
    v.b = fn.y - st.y;
    return v;
}

line ml(point a, point b)
{
    line l;
    l.a = b.y - a.y;
    l.b = a.x - b.x;
    l.c = -l.a * a.x - l.b * a.y;
    return l;
}

typ skalar(vec a, vec b)
{
    return a.a * b.a + a.b * b.b;
}

typ cross(vec a, vec b)
{
    return a.a * b.b - a.b * b.a;
}