#include <bits/stdc++.h>
using namespace std;
 
long long cost(long long x){
    return 3*x*x + 2*x + 1;
}
 
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int t; cin >> t;
    while(t--){
        long long n; cin >> n;
        long long ans = 0;
        for(long long x = 1; n > 0; x *= 3){
            long long k = n % 3; // how many deals of size 3*x
            ans += k * cost(x);
            n /= 3;
        }
        cout << ans << "\n";
    }
}
 

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpsb25nIGxvbmcgY29zdChsb25nIGxvbmcgeCl7CiAgICByZXR1cm4gMyp4KnggKyAyKnggKyAxOwp9CgppbnQgbWFpbigpewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOyBjaW4udGllKDApOwogICAgaW50IHQ7IGNpbiA+PiB0OwogICAgd2hpbGUodC0tKXsKICAgICAgICBsb25nIGxvbmcgbjsgY2luID4+IG47CiAgICAgICAgbG9uZyBsb25nIGFucyA9IDA7CiAgICAgICAgZm9yKGxvbmcgbG9uZyB4ID0gMTsgbiA+IDA7IHggKj0gMyl7CiAgICAgICAgICAgIGxvbmcgbG9uZyBrID0gbiAlIDM7IC8vIGhvdyBtYW55IGRlYWxzIG9mIHNpemUgMyp4CiAgICAgICAgICAgIGFucyArPSBrICogY29zdCh4KTsKICAgICAgICAgICAgbiAvPSAzOwogICAgICAgIH0KICAgICAgICBjb3V0IDw8IGFucyA8PCAiXG4iOwogICAgfQp9Cg==

NwoxCjMKOAoyCjEwCjIwCjI2MDAxMDAwMAo=

7
1
3
8
2
10
20
260010000