#include<stdio.h>
#include<math.h>
#include<string.h>
int temp[410000];
char jz16[110000];
int answer[410000];
int switcha(char a)
{
	if(a>='0'&&a<='9')
	    return a-'0';
	else
	    return a-'A'+10;
}
int main()
{
	int n;
	int len;
	int now;
	int i,j,k;
	int sum;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%s",jz16);
		len=strlen(jz16);
		for(i=0;i<len;i++)
		{
			now=switcha(jz16[i]);
			for(j=(i+1)*4-1;j>=i*4;j--)
			{
				temp[j]=now%2;
				now/=2;
			}
		}//一个十六进制变成4个二进制顺着来 
		memset(answer,0,sizeof(answer));
		for(i=len*4-1,sum=0;i>=0;i-=3,sum++)
		//三个二进制变成一个八进制逆着来 
		    for(j=i,k=0;j>i-3&&j>=0;j--,k++)
		        answer[sum]+=temp[j]*(int)pow(2,k);
		for(i=sum;;i--)
		    if(answer[i]!=0)
		        break;
		//注意不输出前面多余的0 
		for(i=i;i>=0;i--)
		    printf("%d",answer[i]);
		printf("\n");
	}
	return 0;
}