#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define adel_wageeh ios::sync_with_stdio(0), ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
string binary_convert(int morgn_num)
{
string binaryy;
if (morgn_num == 0)
{
binaryy = '0';
return binaryy;
}
while (morgn_num != 0)
{
if (morgn_num % 3 == 0)
binaryy += '0';
else if(morgn_num%3==1)
binaryy += '1';
else
{
binaryy = "-1";
return binaryy;
}
morgn_num /= 3;
}
return binaryy;
}
ll desimal_convert(string s)
{
ll sum=0;
for (int i = 0; i < s.length(); i++)
sum += ((s[i]-48) * pow(2, i));
return sum;
}
int main()
{
adel_wageeh;
string s;
int turns_num,morgn_num;
cin >> turns_num;
while (turns_num)
{
cin >> morgn_num;
s = binary_convert(morgn_num);
if (s == "-1")
{
cout << -1;
return 0;
}
cout << desimal_convert(s) << endl;
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgZW5kbCAiXG4iCiNkZWZpbmUgYWRlbF93YWdlZWggaW9zOjpzeW5jX3dpdGhfc3RkaW8oMCksIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCksIGNpbi50aWUoMCksIGNvdXQudGllKDApOwpzdHJpbmcgYmluYXJ5X2NvbnZlcnQoaW50IG1vcmduX251bSkKewogICAgc3RyaW5nIGJpbmFyeXk7CiAgICBpZiAobW9yZ25fbnVtID09IDApCiAgICB7CiAgICAgICAgYmluYXJ5eSA9ICcwJzsKICAgICAgICByZXR1cm4gYmluYXJ5eTsKICAgIH0KICAgIHdoaWxlIChtb3Jnbl9udW0gIT0gMCkKICAgIHsKICAgICAgICBpZiAobW9yZ25fbnVtICUgMyA9PSAwKQogICAgICAgICAgICBiaW5hcnl5ICs9ICcwJzsKICAgICAgICBlbHNlIGlmKG1vcmduX251bSUzPT0xKQogICAgICAgICAgICBiaW5hcnl5ICs9ICcxJzsKICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICBiaW5hcnl5ID0gIi0xIjsKICAgICAgICAgICAgcmV0dXJuIGJpbmFyeXk7CiAgICAgICAgfQoKICAgICAgICBtb3Jnbl9udW0gLz0gMzsKICAgIH0KICAgIHJldHVybiBiaW5hcnl5Owp9CmxsIGRlc2ltYWxfY29udmVydChzdHJpbmcgcykKeyAKICAgIGxsIHN1bT0wOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBzLmxlbmd0aCgpOyBpKyspCiAgICAgICAgc3VtICs9ICgoc1tpXS00OCkgKiBwb3coMiwgaSkpOwogICAgcmV0dXJuIHN1bTsKfQppbnQgbWFpbigpCnsKICAgIGFkZWxfd2FnZWVoOwogICAgc3RyaW5nIHM7CiAgICBpbnQgdHVybnNfbnVtLG1vcmduX251bTsKICAgIGNpbiA+PiB0dXJuc19udW07CiAgICB3aGlsZSAodHVybnNfbnVtKQogICAgewogICAgICAgIGNpbiA+PiBtb3Jnbl9udW07CiAgICAgICAgcyA9IGJpbmFyeV9jb252ZXJ0KG1vcmduX251bSk7CiAgICAgICAgaWYgKHMgPT0gIi0xIikKICAgICAgICB7CiAgICAgICAgICAgIGNvdXQgPDwgLTE7CiAgICAgICAgICAgIHJldHVybiAwOwogICAgICAgIH0KICAgICAgICBjb3V0IDw8IGRlc2ltYWxfY29udmVydChzKSA8PCBlbmRsOwoKICAgIH0KCn0=