#include <stdio.h>

int pow3(int n) {
	int res =1 ;
	
	for(int i=0; i <n;i++) {
		res *= 3;
	}
	return res;
}

int main() {
	
	int dimensions[30];
	dimensions[0] = 1;
	
	int n;
	scanf("%d", &n);
	/*
	for (int i=1;i < 30; i++) {
		dimensions[i] = 3* dimensions[i-1] + pow3(i-1);
		
	}
	dimensions[0] = 1;
	for (int i=1;i < 13; i++) {
		dimensions[i] *= 2;
		dimensions[i] += pow3(i);
	}*/
	
	for (int i=1;i < 30; i++) {
		dimensions[i] = dimensions[i-1] *3;
	}
	
	
	
	for(int x=0; x < n; x++) {
		int a;
		scanf("%d", &a);
		
		bool print = false;
		
		for(int i = 29; i >=0; i--) {
			int res = a / dimensions[i];
			if(res > 0) {
				print = true;
			}
			
			if(print) {
				printf("%d",res);
			}
			if(i!=0 && print)
				printf(" ");
			a -= dimensions[i] * res;
			
		}
		printf("\n");
	}
	
	
	return 0;
}