# include<stdio.h>
# include<string.h>
void main()
{
int n;
scanf("%d\n",&n);
while(n--){
int i,j=0,num1[64]={0},c=0,k=0,t=0,num2[64]={0};
char str1[64]={' '};
gets(str1);
c=strlen(str1);
for(i=0;i<c;i++){
num1[i]=str1[i]-48;}
while(1){
int r=0;
k=num1[0]%3;
num1[0]=num1[0]/3;
for(i=0;i<c;i++){
t=k;
k=(k*2+num1[i+1])%3;
num1[i+1]=(t*2+num1[i+1])/3;}
num2[j]=t;
j++;
for(i=0;i<c;i++){
if(num1[i]==0) r++;}
if(r==c) break;}
for(i=0;i<j;i++){
printf("%d",num2[j-1-i]);}
printf("\n");
}
}