import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
/**
 *
 * @author cteam084
 */
class Lode {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        int a = Integer.parseInt(br.readLine());

        for (int i = 0; i < a; i++) {

            int number = Integer.parseInt(br.readLine());

            int max = findMax(number);
            while (max != 0) {
                if(number ==0 )
                {
                    bw.write(0 + "");
                    break;
                }
                
                int count = number / max;
               
                number = number % max;
                max = max  / 3;
                if(number > 0)
                bw.write(count + " ");
                else
                 bw.write(count + "");
            }
            bw.write("\n");

        }

        bw.flush();


    }

    public static int findMax(int n) {
        int number = 1;
        
        while(number < n)
        {
            number*=3;
            
        }
        if(n == 1)
            return 1;
        
        
        
        return number/3;
    }
}