#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;



int main(){
	unsigned long pow = 1;
	unsigned long array[15];
	unsigned int N;
	int buffer[15];
	unsigned long K;
	
	
	
	for(int i = 0; i < 15; ++i){
		array[i] = pow;
		pow *= 3;	
	}
	
	
	scanf("%u", &N);
	
	while(N){
		int j = 0;
		for(int i = 0; i < 15; ++i)
			buffer[i] = 0;
		scanf("%lu", &K);
		for(int i = 14; i >= 0; --i){
			if(K >= array[i]){
				buffer[j] = K / array[i];
				K -= array[i] * buffer[j];
			}
			j++;
		}
		--N;
		bool start = false;
		
		for(int i = 0; i < j; ++i){
			if(buffer[i])
				start = true;
			if(i == j-1 && start)
				printf("%d", buffer[i]);
			else
				if(start)
					printf("%d ", buffer[i]);
		}
		printf("\n");
	}
	
	
	




	return 0;

}