import java.util.Scanner;


public class Lode {
	
	static int [] dimsE;
	static int [] dimsV;
	static int [] ceny;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while (sc.hasNextLine()) {
			int k = sc.nextInt();
			sc.nextLine();
			
			int[] num = new int[k];
			
			for (int i = 0; i < k; i++) {
				num[i] = sc.nextInt();
				
				sc.nextLine();
			}
			
			
			for (int i = 0; i < num.length; i++) {
				System.out.println(count(num[i]));
			}
			
			
		}
		

	}

	private static String count(int num) {
		if(num == 1) return "1";
		
		//System.out.println("Num: " + num);
		int d = (int) Math.floor(Math.log(num)/Math.log(3)) + 1;
		//System.out.println("D: " + d);
		
		dimsE = new int[d];
		dimsV = new int[d];
		ceny = new int[d];
		
		countDimensions(d);
		
		int zbytek = num;
		
		StringBuilder out = new StringBuilder();
		
		for (int i = d - 1; i >= 0; i--) {
			out.append((zbytek/dimsV[i]) + " ");
			zbytek %= dimsV[i];
		}
		
		return out.toString().trim();
		
	}

	private static void countDimensions(int d) {
		dimsE[0] = 0;
		dimsV[0] = 1;
		
		for (int i = 1; i < d; i++) {
			dimsV[i] = (int)Math.pow(3, i);
			dimsE[i] = (3 * dimsE[i - 1]) + (2 * dimsV[i - 1]);
			ceny[i] = dimsV[i] + dimsE[i];
		}
	}
	
	

}