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

using namespace std;
#define FOR(i,n) for(int i = 0; i < n; i++)
int main(void){
	int w[15];
	w[0] = 1;
	for(int i = 1; i < 15; i++){
		w[i] = 3*w[i-1];
	}
	
	int n;
	int out[15];
	scanf(" %d",&n);
	FOR(i,n){
		int k;
		scanf(" %d",&k);
		int index = 14;
		int start_print = 0;
		while(index >= 0){
			out[index] = k / w[index];
			k %= w[index];
			start_print = start_print || out[index];
			if(start_print){
					if(index == 0){
						printf("%d", out[index]);
					}else{
						printf("%d ", out[index]);
					}
			}
			index--;
		}
		printf("\n");
	}
	return 0;
}