/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package lode;

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

/**
 *
 * @author cteam042
 */
public class Lode {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int tests = Integer.parseInt(in.nextLine());
        int[] ourtests = new int[tests];
        int max = 0;

        for (int i = 0; i < tests; i++) {
            ourtests[i] = Integer.parseInt(in.nextLine());
            if (ourtests[i] > max) {
                max = ourtests[i];
            }
        }

        ArrayList<Integer> mocninytrojky = new ArrayList<Integer>();
        int a = 1;
        mocninytrojky.add(a);
        for (int i = 0; a < max; i++) {
            
            a *= 3;
            mocninytrojky.add(a);
        }
        boolean end = false;
        for (int i = 0; i < tests; i++) {
            int j = 0;
            while(!end){
                if (mocninytrojky.get(j) > ourtests[i]) {
                    j--;
                    while(j != -1) {
                       if (2 * mocninytrojky.get(j) <= ourtests[i]) {
                           System.out.format("2 ");
                           ourtests[i] -= 2 * mocninytrojky.get(j);
                       } else {
                       if ( mocninytrojky.get(j) <= ourtests[i]) {
                            System.out.format("1 ");
                            ourtests[i] -=  mocninytrojky.get(j);
                       } else {
                            System.out.format("0 ");
                       }
                       }
                               j--;
                    }
                    break;
                }
                j++;
                
            }
            System.out.println();
        }
    }
}