#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;

vector<long> vert;
vector<long> edge;

int main() {
  vert.push_back(1);
  //edge.push_back(0);
  while (vert.back() <= 10000000) {
    //edge.push_back(3*edge.back() + 2*vert.back());
    vert.push_back(vert.back() * 3);
  }

  int N; cin >> N;
  while (N--) {
    long K; cin >> K;

    long i = vert.size() - 1;
    while (K < vert[i]) --i;
    for (; i >= 1; --i) {
      int num = K / vert[i];
      cout << num << " ";
      K -= num * vert[i];
    }
    cout << K;
    cout << "\n";
  }

  return 0;
}