#include<stdio.h>

#include<string.h>

#include<math.h>

#include<stdlib.h>

#include<queue>

#include<stack>

#include<algorithm>

using namespace std;

int f[][];

int n;

void dabiao()

{

    int i,j,k;

    memset(f,,sizeof(f));

    f[][]=;

    f[][]=;

    for(i=; i<=; i++)

    {

        for(j=; j<=; j++)

        {

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

        }

        for(j=;j<=;j++)

        {

            if(f[i][j]>=)

            {

                f[i][j+]++;

                f[i][j]-=;

            }

        }

    }

}

int main()

{

    int n,m,i,j,k,t;dabiao();

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        int flag=;

        for(i=;i>=;i--)

        {

            if(flag==||f[n][i])

            {

                printf("%d",f[n][i]);

                flag=;

            }

        }

        printf("\n");

    }

}