#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    const int MAX_I = 25;
    long long costo[MAX_I + 1];
    long long p3[MAX_I + 2]; // we need up to index MAX_I+1
 
    // Precompute powers of 3
    p3[0] = 1;
    for (int i = 1; i <= MAX_I + 1; i++) {
        p3[i] = p3[i - 1] * 3;
    }
 
    // Precompute costo for i from 0 to MAX_I
    costo[0] = 3;
    for (int i = 1; i <= MAX_I; i++) {
        costo[i] = p3[i + 1] + i * p3[i - 1];
    }
 
    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        vector<int> digits;
        long long temp = n;
        while (temp) {
            digits.push_back(temp % 3);
            temp /= 3;
        }
        long long ans = 0;
        for (int i = 0; i < digits.size(); i++) {
            ans += digits[i] * costo[i];
        }
        cout << ans << endl;
    }
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKSB7CiAgICBjb25zdCBpbnQgTUFYX0kgPSAyNTsKICAgIGxvbmcgbG9uZyBjb3N0b1tNQVhfSSArIDFdOwogICAgbG9uZyBsb25nIHAzW01BWF9JICsgMl07IC8vIHdlIG5lZWQgdXAgdG8gaW5kZXggTUFYX0krMQoKICAgIC8vIFByZWNvbXB1dGUgcG93ZXJzIG9mIDMKICAgIHAzWzBdID0gMTsKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IE1BWF9JICsgMTsgaSsrKSB7CiAgICAgICAgcDNbaV0gPSBwM1tpIC0gMV0gKiAzOwogICAgfQoKICAgIC8vIFByZWNvbXB1dGUgY29zdG8gZm9yIGkgZnJvbSAwIHRvIE1BWF9JCiAgICBjb3N0b1swXSA9IDM7CiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBNQVhfSTsgaSsrKSB7CiAgICAgICAgY29zdG9baV0gPSBwM1tpICsgMV0gKyBpICogcDNbaSAtIDFdOwogICAgfQoKICAgIGludCB0OwogICAgY2luID4+IHQ7CiAgICB3aGlsZSAodC0tKSB7CiAgICAgICAgbG9uZyBsb25nIG47CiAgICAgICAgY2luID4+IG47CiAgICAgICAgdmVjdG9yPGludD4gZGlnaXRzOwogICAgICAgIGxvbmcgbG9uZyB0ZW1wID0gbjsKICAgICAgICB3aGlsZSAodGVtcCkgewogICAgICAgICAgICBkaWdpdHMucHVzaF9iYWNrKHRlbXAgJSAzKTsKICAgICAgICAgICAgdGVtcCAvPSAzOwogICAgICAgIH0KICAgICAgICBsb25nIGxvbmcgYW5zID0gMDsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IGRpZ2l0cy5zaXplKCk7IGkrKykgewogICAgICAgICAgICBhbnMgKz0gZGlnaXRzW2ldICogY29zdG9baV07CiAgICAgICAgfQogICAgICAgIGNvdXQgPDwgYW5zIDw8IGVuZGw7CiAgICB9CiAgICByZXR1cm4gMDsKfQ==

MwoxMAoyNgo2CjM2CjcyCjIyNTA5NjQ3MjgK

3
10
26
6
36
72
2250964728