hdu1715

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int f[1005][605];

void solve(){
	f[1][0] = f[2][0] = 1;
	f[1][1] = f[2][1] = 1;
	int len = 1;
	for (int i = 3; i <= 1000; i++){
		for (int j = 1; j <= len; j++){
			f[i][j] += f[i - 1][j] + f[i - 2][j];
			if(f[i][j] >= 10){
				f[i][j + 1] += f[i][j] / 10;
				f[i][j] %= 10;
			}
		}
		while(f[i][len + 1]){
			len++;
		}
		f[i][0] = len;
	}
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	int n, t;
	solve();
	scanf("%d", &t);
	while(t--){
		scanf("%d", &n);
		for (int i = f[n][0]; i >= 1; i--){
			printf("%d", f[n][i]);
		}
		printf("\n");
	}

	return 0;
}
/**/