import java.util.Scanner;

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
/**
 *
 * @author drevenak3
 */
public class Lode {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String line;
        int n=scan.nextInt();
        for (int i = 1; i <=n; i++) {
            long k=scan.nextLong();
            StringBuilder s=new StringBuilder("");
            while(k>0){
                if((k%3)==0)
                    s.append("0");
                else if((k%3)==1)
                    s.append("1");
                else
                    s.append("2");
                k=k/3;
                s.append(" ");
            }
            s.deleteCharAt(s.length()-1);
            System.out.println(s.reverse().toString());
        }
    }
}