#include<iostream>

#include<cstring>

#include<cmath>

#include<queue>

#include<algorithm>

#include<cstdio>

#define max(a,b) a>b?a:b

using namespace std;

#define LL long long

#define INF 0x3f3f3f3f

int fib[][];

void cal()

{

    fib[][]=fib[][]=;

    fib[][]=fib[][]=;

    int i,j,num=;

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

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

            int num1=fib[i-][j]+fib[i-][j]+fib[i][j];

            fib[i][j]=num1%;

            fib[i][j+]=num1/;

        }

        if(fib[i][num])num++;

        fib[i][]=num-;

    }

}

int main()

{

    memset(fib,,sizeof(fib));

    cal();

    int n,m;

    scanf("%d",&n);

    while(n--)

    {

        scanf("%d",&m);

        for(int i=fib[m][];i>;i--)

        {

            printf("%d",fib[m][i]);

        }

        printf("\n");

    }

    return ;

}