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

const int maxLode = 16;

int N, lodMax;
int lode[maxLode];
int pom;
bool prva;
//int lodi[maxLode];
//struct lod lode[maxLode];
//
//struct lod {
//	int palicky;
//	int gulicky;
//};

int main() {
	//// nachystam si lode
	//lode[0].palicky =0;
	//lode[0].gulicky = 1;

	//for (int i=1; i < maxLode; i++) {
	//	lode[i].gulicky = 3 * lode[i-1].gulicky;
	//	//lode[i].palicky = 3 * lode[i-1].palicky + 2 * lode[i-1].gulicky;
	//}
	//



	
  scanf("%d\n", &N);

  for (;N>0;N--){
	scanf("%d\n", &lodMax); // kapacita
	
	/*for (int i = 0; i < maxLode; i++) {
		lodi[i] = -1;
	}*/
	pom = 0;
	for (int i=0; i < maxLode; i++) {
		lode[i] = -1;
	}

	while (lodMax > 0) {
	    lode[pom] =  lodMax % 3;
		lodMax = lodMax / 3;
		pom++;
	}

	prva = true;
	for (int i = maxLode -1 ; i>=0; i--) {
		if (lode[i] > -1) {
			if (prva) {
				prva = false;
			} else {
				printf(" ");
			}

			printf("%d", lode[i]);
		}
	}

	printf("\n");
  }
  return 0;
}