/*
 *  Copyright (c) 2025 Parag Kishor Shornob
 *   All rights reserved.
 */
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<long long > vi;
typedef pair<int,int> pii;
 
#define yes "YES\n"
#define no "NO\n"
#define pb push_back
#define pop pop_back
#define fastin ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define input(v) for(auto &i  : v) cin>>i;
#define all(x) (x).begin(),(x).end()
 
char ee = '\n';
void printVec(vector<ll> &a){
    for(auto pp : a) cout<<pp <<" " ;
    cout<<ee;
}
ll power(ll base , ll exp){   
    ll result=1;
    while(exp>0){
       if(exp%2==1){
        result *=base;
       }
       base  *=base ;
       exp/=2;
 
    }
    return result;
 
}
ll cost(ll n ){
    return power(3,n+1)+ n*power(3,n-1);
}
ll base (ll n ){
     ll ans =0 , base =1;
     while(base *3<=n){
        base *=3;
        ans++;
        
     }
    return ans;
}
void  solve(){
   ll n ; cin>>n ;
   ll ans =0;
   while(n>0){
    //ll p = log(n)/log(3);
    ll p = base (n);
    ans+=cost(p);
    n-=power(3,p);
 
   }
   cout<<ans<<ee;
 
}
signed main() {
    fastin; 
    ll tt=1 ; cin>> tt;
    while(tt--) solve();
  
}