#include<iostream>
#include <vector>
using namespace std;

int main(int a, char **b) {
	int n;
	cin >> n;
	for (int i = 0 ; i<n ; ++i) {
		unsigned x;
		cin >> x;
		unsigned pow = 1;
		while (pow <= x) {
			pow *= 3;
		}
		pow /= 3;
		while (pow > 0) {
			cout << x/pow;
			x = x%pow;
			if (pow < 3) break;
			pow /= 3;
			cout << " ";
		}
		cout << endl;
	}
	return 0;
}