#include <stdio.h>
#include <stdlib.h>

int main()
{
int pocet, v, i,j, cislo, p;
int zapC;

scanf("%d", &pocet);

if(pocet <= 0){
return 0;
}
int bmm=0;
for(i = 0; i < pocet; i++){
	bmm =0;
	scanf("%d", &cislo);
	if(cislo <0){
		bmm=1;
	}
	if(cislo == 0){
		printf("0");
	}
	p = 0;
	if(cislo >= 10000000){
		return 0;
	}
	zapC = cislo;
	while(cislo != 0 && cislo > 0){
		cislo = cislo/3;
		p++;	 	
	}

	int pole[p];

	for(j = 0; j < p; j++){
		v = zapC%3;
		zapC = zapC/3;
		pole[j] = v;	 	
	}
	
	while(p!=0){	
		p--;
		printf("%d ", pole[p]);
	}
        if(bmm == 0){
	printf("\n");}	
		
}
    return 0;
}