#include <iostream>
#define FOR(i,a,b) for ( int i = int(a); i <= int(b); ++i )
#define FORD(i,a,b) for ( int i = int(a); i >= int(b); --i )
#define REP(i,n) for ( int i = 0; i < int(n); ++i )
using namespace std;

typedef unsigned long long ull;

ull res[1000];

int main( ) {
  ios::sync_with_stdio( 0 );
  int t, n;
  cin >> t;
  
  res[0] = 1;
  int len = 1;
  for ( ; res[len] <= 10000000; len++)
    res[len] = 3*res[len-1];
  //cout << res[len] << " " << len<<endl;
while ( t-- ) {
  cin >> n;
  bool first = false;
  for ( int i = len; i>=0; i--) {
    if ( n/res[i] > 0 || first ) {
      if ( first ) cout << " ";
      cout << n/res[i];
      n= n%res[i];
      first = true;
    }
  }
  cout << endl;

}
  
	return 0;
}