#include <iostream>
#include <cstdio>

using namespace std;

int main() {
	int n_inputs;
	cin >> n_inputs;
	

	int cargo_out[100000];
	int count;
	for (int i = 0; i < n_inputs; i++) {
		count = 0;
		int cargo_cap;
		cin >> cargo_cap;
		while (cargo_cap > 0) {
			cargo_out[count++] = cargo_cap % 3;
			cargo_cap /= 3;
		}

		for (int j = count - 1; j >= 0; j--) {
			cout << cargo_out[j];
			if (j != 0) cout << " ";
			else cout << endl;
		}
	}
	

	return 0;
}