#include<iostream>

#include<cstdio>

#include<cmath>

#define Rg register

#define il inline

#define db double

#define ll long long

#define go(i,a,b) for(Rg int i=a;i<=b;i++)

#define yes(i,a,b) for(Rg int i=a;i>=b;i--)

using namespace std;

il int read()

{

    int x=,y=;char c=getchar();

    while(c<''||c>''){if(c=='-')y=-;c=getchar();}

    while(c>=''&&c<=''){x=(x<<)+(x<<)+c-'';c=getchar();}

    return x*y;

}

int T,n,d,k;

ll f[][];

il void init()

{

    f[][]=;

    go(i,,)

    {

        f[i][]=*(f[i-][]+f[i-][]+f[i-][]);

        f[i][]=f[i-][];

        f[i][]=f[i-][];

        f[i][]=f[i-][]+*f[i-][];

    }

}

int main()

{

    init();T=read();

    while(T--)

    {

        n=read();d=;k=;

        while(f[d][]<n)d++;

        yes(i,d,)

        {

            go(j,,)

            {

                //求若第i位为j,那么剩下i-1位有多少种填法能使这个数成为魔鬼数

                ll ct=f[i-][];

                if(j== || k>=)

                    go(t,max(,-k-(j==)),)ct+=f[i-][t];

                if(ct<n)n-=ct;//应该填一个更大的数

                else //就填j

                {

                    if(j==)k++;else if(k<)k=;

                    printf("%d",j);break;

                }

            }

        }

        printf("\n");

    }

    return ;

}