const LL MAXV=1e12+5,MAXN=1e6;
vector<LL> vec;
LL dp[MAXN];
void Init(){
	vec.push_back(1);
	LL base=6;
	while(base<MAXV){
		vec.push_back(base);
		base*=6;
	}
	base=9;
	while(base<MAXV){
		vec.push_back(base);
		base*=9;
	}
	sort(vec.begin(),vec.end());
	_for(i,1,MAXN){
		dp[i]=i;
		for(int v:vec){
			if(v<=i)
			dp[i]=min(dp[i],dp[i-v]+1);
			else
			break;
		}
	}
}
LL ans;
void dfs(LL x,int pos,int step){
	if(x<MAXN){
		ans=min(ans,dp[x]+step);
		return;
	}
	if(pos==0){
		ans=min(ans,x+step);
		return;
	}
	LL m=x/vec[pos];
	for(int i=m;i>=0;i--){
		if(m+step>=ans)return;
		dfs(x-i*vec[pos],pos-1,step+i);
	}
}
int main()
{
	Init();
	int T=read_int();
	while(T--){
		LL x=read_LL();
		ans=1e9;
		dfs(x,vec.size()-1,0);
		enter(ans);
	}
	return 0;
}