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

int main()
{

int max;
max = 1000000;
int pocet, v, i, cislo, pole[max], p;

scanf("%d", &pocet);

if(pocet <= 0){
return 0;
}

for(i = 0; i < pocet; i++){

	scanf("%d", &cislo);
	if(cislo <0){
		return 0;
	}
	if(cislo == 0){
		printf("0");
	}
	p = 0;
	if(cislo<0 || cislo >= 10000000){
		return 0;
	}
	
	while(cislo != 0){
	
		v = cislo%3;
		cislo = cislo/3;
		pole[p] = v;
		p++;	 	
	}
	while(p!=0){	
		p--;
		printf("%d ", pole[p]);
	}
	printf("\b\n");
		
}
    return 0;
}