#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;

#define PB push_back
#define MP make_pair

#define FOR(prom, a, b) for(int prom = (a); prom < (b); prom++)
#define FORD(prom, a, b) for(int prom = (a); prom > (b); prom--)
#define FORDE(prom, a, b) for(int prom = (a); prom >= (b); prom--)

#define MM(co, cim) memset((co), (cim), sizeof((co)))
#define DEB(x) cerr << ">>> " << #x << " : " << x << endl;

#define MAXD 20

int points [ MAXD ];

int main ( void )
{
	int N, K;

	points[ 0 ] = 1;
	int maxd = 0;

	scanf( "%d", &N );
	for ( int n = 0; n < N; n++ ) {
		scanf( "%d", &K );

		while ( points[ maxd ] < K ) {
			maxd++;
			points[ maxd ] = 3 * points[ maxd - 1 ];
		}

		for ( int d = ( log( K ) / log( 3 ) ); d >= 0; d-- ) {
			printf( "%d", K / points[ d ] );
			K = K % points[ d ];
			if ( d != 0 ) {
				printf(" ");
			}
		}

		printf( "\n" );
	}


	return 0;
}