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

int values[1000];
int maxindex;

void prepare()
{
  for (int i = 0, j = 1; i < 1000 && j < 10000000; i++, j*=3)
  {
    values[i] = j;
    maxindex = i;
  }
}

int main()
{
  prepare();
  int count;
  scanf("%d", &count);
  for (int i = 0; i < count; i++)
  {
    int tonnage;
    scanf("%d", &tonnage);
    int printing = 0;
    for (int j = maxindex; j >= 0; j--)
    {
      int plus;
      if (tonnage >= values[j])
      {
        plus = tonnage / values[j];
	//printf("+%d", plus);
      }
      else
        plus = 0;
      if (plus > 0)		   
      {
	printing++;
	tonnage -= plus * values[j];
      }
      else
      {
	if (printing)
	  printing++;
      }
   
      if (printing)
      {
	if (printing > 1)
	  printf(" ");
	printf("%d", plus);
      }
    } 
    printf("\n");
  }
  return 0;
}