#include <iostream>
#include <bitset>
#include <string>
#include <algorithm>

using namespace std;

int is_pinary(long long n)
{
    long long l=0;
    while (n)
    {
        long long r = (1&n);
        if (r&&l) return 0;
        if (!r && l) l =0;
        if (r && !l) l =1;
        n>>=1;
    }
    return 1;
}

int bits[] = { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,
 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393,
 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887,
 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141};

int main()
{
    long long n,cases;
    scanf("%lld\n",&cases);
    while (cases-- && scanf("%lld\n",&n)==1) 
    {
        long long start = n;
        long long res=0;
        while (n>1)
        {
            long long i=0;
            while (bits[i]<n) i++;
            n-=bits[i-1];
            i-=2;
            res+=(long long)1<<i;
        }
        res+=1;
        while (!is_pinary(res))
        {
            res++;
        }
        bitset<100> a=res;
        string ans = a.to_string();
        while (ans[0]=='0') ans.erase(0,1);
        printf("%s\n",ans.c_str());
        //cout << ans << endl;
        /*
        long long wrk=0;
        long long count=0;
        while (count<start)
        {
            wrk++;
            if (is_pinary(wrk)) count++;
            
        }
        a=wrk;
        ans = a.to_string();
        while (ans[0]=='0') ans.erase(0,1);
        cout << ans << endl;*/
    }
}