#include<iostream>
#include<string>
using namespace std;
string getTwo(string data);
void getEight(string data);
int main(int argc,char** argv){
int nums;
string data;
cin >> nums;
for(int i = 0;i < nums;i++){
data = "";
cin >> data;
getEight(getTwo(data));
}
return 0;
}
string getTwo(string data){
string resault = "";
for(int i = 0;i < data.length();i++)//遍历，字符串上加上每一位
{
switch(data[i])
{
case '0':resault+="0000";break;
case '1':resault+="0001";break;
case '2':resault+="0010";break;
case '3':resault+="0011";break;
case '4':resault+="0100";break;
case '5':resault+="0101";break;
case '6':resault+="0110";break;
case '7':resault+="0111";break;
case '8':resault+="1000";break;
case '9':resault+="1001";break;
case 'A':resault+="1010";break;
case 'B':resault+="1011";break;
case 'C':resault+="1100";break;
case 'D':resault+="1101";break;
case 'E':resault+="1110";break;
case 'F':resault+="1111";break;
default:break;
}
}
return resault;
}
void getEight(string data){
int length = data.length();
int flag = 0;
if(length % 3 == 0){
}else if(length % 3 == 1){
data = "00" + data;
length = data.length();
}else if(length % 3 == 2){
data = "0" + data;
length = data.length();
}
for(int i = 0;i < length;i = i + 3){
int value = 4 * (data[i] - '0') + 2 * (data[i + 1] - '0') + (data[i + 2] - '0');
if(value){
flag = 1;
}
if(flag){
cout << value;
}
}
cout << endl;
}
