package javaapplication1;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Lode {

    static int[] dim = new int[16];

    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        dim = dimw();
        ArrayList<Integer> res;
        long cases = scn.nextLong();
        for(int c = 0;c<cases;c++) {
            res = compute(scn.nextInt());
            for (int i = 0; i < res.size(); i++) {
                System.out.print(res.get(i));
                if (i < res.size() - 1) {
                    System.out.print(" ");
                } else {
                    System.out.print("\n");
                }
            }
        }
    }

    public static ArrayList<Integer> compute(int w) {
        ArrayList<Integer> r = new ArrayList<Integer>();
        int q = 0;
        for (int i = 15; i >= 0; i--) {
            if (w / dim[i] >= 1) {
                q = i;
                break;
            }
        }
        for (int i = q; i >= 0; i--) {
            r.add((int) w / dim[i]);
            w = w % dim[i];


        }
        return r;
    }

    public static int[] dimw() {
        dim[0] = 1;
        for (int i = 1; i <= 15; i++) {
            dim[i] = dim[i - 1] * 3;
        }
        return dim;
    }
}