#include<iostream>
#include<string>
#define MAXN 10
using namespace std;

string converseToBinary(string hex){
	string bin;
	for (int i = 0; i < hex.length(); i++){
		switch(hex[i]){
		case '0':bin += "0000";break;
		case '1':bin += "0001";break;
		case '2':bin += "0010";break;
		case '3':bin += "0011";break;
		case '4':bin += "0100";break;
		case '5':bin += "0101";break;
		case '6':bin += "0110";break;
		case '7':bin += "0111";break;
		case '8':bin += "1000";break;
		case '9':bin += "1001";break;
		case 'A':bin += "1010";break;
		case 'B':bin += "1011";break;
		case 'C':bin += "1100";break;
		case 'D':bin += "1101";break;
		case 'E':bin += "1110";break;
		case 'F':bin += "1111";break;
		default :break;
		}
	}
	return bin;
}

void outputOctString(string bin){
	string oct;
	int count = 0 ;
	int num = 0;
	char temp;
	for (int i = bin.length()-1; i>=0;i--)	{
		if(bin[i]=='1'){
			switch(count){
			case 0: num += 1;break;
			case 1: num += 2;break;
			case 2: num += 4;break;
			}
		}
		if(count==2){
			oct += num + '0';
			num = 0;
		}
		count = (count+1)%3;
	}
	if(count!=0){
		oct += num + '0';
	}
	int len = oct.length();
	for(int j=0;j<len/2;j++){
		temp = oct[j];
		oct[j] = oct[len-1-j];
		oct[len-1-j] = temp; 
	}
	int index = 0;
	//忽略前导零
	while(oct[index++] == '0');
	/* 这里表问我为啥这样写，因为不这样写，傻逼测评系统不给过*/
	for(index=index-1;index<len;index++){
		printf("%c",oct[index]);
	}
	printf("\n");
}


int main(){
	int n;
	string hex[10];
	string bin;
	cin>>n;
	for (int i = 0; i < n; ++i){
		cin>>hex[i];
	}
	for (int i = 0; i < n; ++i)	{
		bin = converseToBinary(hex[i]);
		outputOctString(bin);
	}
	return 0;
}