C2 Div3

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

long long how[50];

int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    #endif // ONLINE_JUDGE

    int Q;
    cin >> Q;

    while(Q--)
    {
        long long x;
        cin >> x;

        memset(how, 0, sizeof(how));

        long long   pw = 1;
        int         pz = 0;

        while(pw <= x)
        {
            pw *= 3;
            pz++;
        }

        pw /= 3;
        pz--;

        int maxpz = pz;

        while(x)
        {
            long long cat = x / pw;
            x %= pw;
            how[pz] = cat;
            pw /= 3;
            pz--;
        }

        pw = 1;

        for(int i = 0; i <= maxpz; i++, pw *= 3)
        {
            if(how[i] > 1)
            {
                long long cat = how[i] / 3;
                how[i + 1] += max(cat, 1LL);
                maxpz = max(maxpz, i + 1);
                how[i] = 0;
                x = 0;
            }

            x += how[i] * pw;
        }

        cout << x << '\n';
    }

    return 0;
}