#include<stdio.h>
#include<math.h>
#include<string.h>
char str[100010];
int s1[200010],s2[400010],s3[200010];
int main()
{
	int i,j,k,n,len,h,sum,flag,u;
	scanf("%d",&n);
	getchar();
	while(n--)
	{
		scanf("%s",str);
		memset(s1,0,sizeof(s1));
		memset(s2,0,sizeof(s2));
		len=strlen(str);
		k=0;j=0;flag=0;
		for(i=0;i<len;i++)
		{
			if(str[i]!='0')
			{
				flag=1;
				break;
			}
		}
		if(!flag)
		{
			printf("0\n");
			continue;
		}
		for(i=len-1;i>=0;i--)
		{
			if(str[i]>='0'&&str[i]<='9')
			{
				s1[k]=str[i]-'0';
				if(s1[k]==0)
				{
					for(u=1;u<=4;u++)
					{
						s2[j++]=0;
					}
				}
				while(s1[k])
				{
					s2[j]=s1[k]%2;
					s1[k]/=2;
					j++;
				}
				while(j%4!=0)
					s2[j++]=0;
				k++;
			}
			if(str[i]>='A'&&str[i]<='F')
			{
				s1[k]=str[i]-'A'+10;
				while(s1[k])
				{
					s2[j]=s1[k]%2;
					s1[k]/=2;
					j++;
				}
				
				while(j%4!=0)
					s2[j++]=0;
				k++;
			}	
		}
		h=0;sum=0;k=1;
		for(i=0;i<j;i++)
		{
			sum+=k*s2[i];
			k*=2;
			if((i+1)%3==0)
			{
				s3[h++]=sum;
				sum=0;
				k=1;
			}
			if(i==j-1&&(i+1)%3!=0)
			{
				s3[h++]=sum;
				sum=0;
				k=1;
			}
		}
		j=h-1;
		for(i=h-1;i>=0;i--)
		{
			if(s3[i]!=0)
				break;
			j--;
		}
		for(i=j;i>=0;i--)
			printf("%d",s3[i]);
		printf("\n");
	}
	return 0;
}

十六进制一位可以化成四位二进制，然后再三个三个取转化成八进制。