#include <iostream>
using namespace std;
int answer[12];
int main() {
	int T;
	scanf_s("%d", &T);
	answer[1] = 1;
	answer[2] = 2;
	answer[3] = 4;
	while (T--) {
		int n;
		scanf_s("%d", &n);
		for (int i = 4; i <= n; i++) {
			answer[i] =  answer[i - 1]+ answer[i - 2]+  answer[i - 3];
		}
		cout << answer[n] << "\n";
	}
	return 0;
}

#include <iostream>
using namespace std;
#include <algorithm>

int main() {
	long long answer[101][10] = { {},{0,1,1,1,1,1,1,1,1,1} };
	long long modd = 1000000000;
	int n;
	scanf_s("%d", &n);

	for (int i = 2; i <= n; i++) {
		for (int j = 0; j < 10; j++) {
			if (j == 0) {
				answer[i][j] = answer[i - 1][j+1] % modd;
			}				
			else if (j == 9) {
				answer[i][j] = answer[i - 1][j-1] % modd;
			}
			else {
				answer[i][j] = (answer[i - 1][j-1]+ answer[i - 1][j+1])%modd;
			}
		}
	}

	long long sum = 0;
	for (int i = 0; i < 10; i++) {
		sum = (sum + answer[n][i]) % modd;
	}
	cout << sum << "\n";
	
	return 0;
}



//https://www.acmicpc.net/source/4408282
//필요없는 부분은 굳이 저장을 하지 않아도 됨
#include <cstdio>
#define R 1000000000
int n,s,k=1,d[2][11];
int main() {
	int i,j;
	for(j=1; j<=9; j++) d[k][j] = 1;
	scanf("%d", &n);
	for(i=2; i<=n; i++) {
		k = !k;
		for(j=0; j<10; j++) d[k][j] = (d[!k][j-1] + d[!k][j+1]) % R;
	}
	for(j=0; j<10; j++) s = (s+d[k][j]) % R;
	printf("%d", s);
	return 0;
}

#include <iostream>
using namespace std;
#include <algorithm>

int main() {
	long long answer[2][10] = { { 1, 1,1,1,1,1,1,1,1,1},{0,} };
	long long modd = 10007;

	int n, b = 0;
	scanf_s("%d", &n);
	for (int k = 1; k < n; k++) { //횟수
		b = !b;
		for (int i = 0; i < 10; i++) { //끝자리수가 0부터 9까지
			answer[b][i] = 0;
			for (int j = 0; j <= i; j++) {
				answer[b][i] = (answer[b][i] + answer[!b][j]) % modd;
			}
		}
	}

	long long sum = 0;
	for (int i = 0; i < 10; i++) {
		sum = (sum + answer[b][i]) % modd;
	}
	cout << sum;

	return 0;
}


//https://www.acmicpc.net/source/4408448
#include <cstdio>
int n,d[15]={1};
int main() {
	int i,j;
	scanf("%d", &n);
	for(i=0; i<=n; i++)
		for(j=1; j<10; j++) 
            d[j]+=d[j-1], d[j]%=10007;
	printf("%d", d[9]);
	return 0;
}

#include <iostream>
using namespace std;

int main() {
	long long answer[2] = { 0,1 };
	int n = 0;
	scanf_s("%d", &n);

	for (int i = 1; i < n; i++) {
		long long ans = answer[1];
		answer[1] = answer[0];
		answer[0] = answer[0] + ans;
	}

	cout << answer[0] + answer[1];
	return 0;
}

// https://www.acmicpc.net/source/16165942
// 규칙을 알고 피보나치수로 간단하게 줄임
#include <stdio.h>
int main(){
	long long  a[91], n;
	scanf("%lld",&n);
	a[1]=1;
	a[2]=1;
	for(int i=3;i<=n;i++) a[i]=a[i-1]+a[i-2];
	printf("%lld", a[n]);
}