#include <iostream>
#include <math.h>
#include <fstream>
using namespace std;
int arr[20]={1,3,9,27,81,243,729,2187,6561,19683,59049,177147,531441,1594323,4782969,14348907,43046721,129140163,387420489,1162261467};
int weight;

int cmp(const void *a1,const void *a2){
	return ( *(int *)a2 -*(int *)a1     );
}

void cal(){
	int lweight=weight;
	int rweight=0;
	int lpart[10],rpart[10];
	int ln=0,rn=0;
	for(int i=19;i>=0&&lweight!=rweight;i--){
		int tmplr=0;
		bool lh=true;
		if(lweight>rweight){
			tmplr=lweight-rweight;
		}else{
			tmplr=rweight-lweight;
			lh=false;
		}
		if(arr[i]<=tmplr){
			if(lh){
				rweight+=arr[i];
				lpart[ln++]=arr[i];
			}else{
				lweight+=arr[i];
				rpart[rn++]=arr[i];
			}
		}else{
			int sum=0;
			for(int j=0;j<i;j++)
				sum+=arr[j];
			if(arr[i]>(sum+tmplr))continue;
			if(lh){
				rweight+=arr[i];
				lpart[ln++]=arr[i];
			}else{
				lweight+=arr[i];
				rpart[rn++]=arr[i];
			}

		}
		
	}
	if(rn==0){
		cout<<"empty"<<" ";
	}else{
		qsort(rpart,rn,sizeof(rpart[0]),cmp);
		for(int tmp=rn-1;tmp>0;tmp--){
			cout<<rpart[tmp]<<",";
		}
		cout<<rpart[0]<<" ";
	}

	if(ln==0){
		cout<<"empty"<<endl;
	}else{
		qsort(lpart,ln,sizeof(lpart[0]),cmp);
		for(int tmp=ln-1;tmp>0;tmp--){
			cout<<lpart[tmp]<<",";
		}
		cout<<lpart[0]<<endl;
	}

}


void main(){
	int testcase;
	cin>>testcase;
	for(int i=0;i<testcase;i++){
		cin>>weight;
		cal();
	}
/*	ofstream out("result.txt");
	for(int i=0;i<=19;i++){
		int res=1;
		for(int j=0;j<i;j++)
			res=res*3;
		out<<res<<",";

	}
*/


}