#include<bits/stdc++.h>
#define int long long
int dp[100005];
using namespace std;
void node(){
	int x;
	cin>>x;
	for(int i=1;i<=x;i++){
		if(i==1){
			dp[i]=1;
			continue;
		}
		if(i==2){
			dp[i]=1;
			continue;
		}
		dp[i]=dp[i-1]+dp[i-2];
	}
	cout<<dp[x]；//写错了，没换行
}
signed main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		node();
	}
}

#include<bits/stdc++.h>
#define int long long
int dp[100005];
using namespace std;
void node(){
	int x;
	cin>>x;
	for(int i=1;i<=x;i++){
		if(i==1){
			dp[i]=1;
			continue;
		}
		if(i==2){
			dp[i]=1;
			continue;
		}
		dp[i]=dp[i-1]+dp[i-2];
	}
	cout<<dp[x]<<endl;
}
signed main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		node();
	}
}

#include<bits/stdc++.h>
#define int long long
int dp[50][50];
using namespace std;
signed main(){
	int n;
	cin>>n;
	dp[1][1]=1;
	cout<<dp[1][1]<<endl;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=i;j++){
			dp[i][j]=dp[i-1][j]+dp[i - 1][j-1];
			cout << dp[i][j] << ' ';
		}
		cout<<endl;
	}
}

#include<bits/stdc++.h>
#define int long long
int a[1000000];
int dp[1000000];
using namespace std;
signed main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int maxx=1;
	for(int i=1;i<=n;i++){
		dp[i]=1;
		for(int j=1;j<=i;j++){
			if(a[i]>a[j]){
				dp[i]=max(dp[i],dp[j]+1); 
			}
		}
		maxx=max(maxx,dp[i]);
	}
	cout<<maxx;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
	int n;
	cin>>n;
	int minn=1e9;
	int flag=0;
	for(int i=0;i<=5000;i++){
		for(int j=0;j<=5000;j++){
			if(i*3+j*5==n){
				minn=min(i+j,minn);
				flag=1;
			}
		}
	}
	if(flag==1){
		cout<<minn;
	}
	else{
		cout<<-1;
	}
}

#include<bits/stdc++.h>
#define int long long
int dp[100005];
using namespace std;
signed main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		dp[i]=1; 
		for(int j=1;j<=i/2;j++){
			dp[i]+=dp[j];
		}
	} 
	cout<<dp[n];  
}

#include <assert.h>
#include <ctype.h>
#include <errno.h>
#include <float.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <wchar.h>
#include <wctype.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#define tin int
#define itn int
#define tni int
#define nit int
#define nti int
#define pritnf printf
#define scnaf scanf
#define int long long
using namespace std ;
signed main()
{
//	std::ios::sync_with_stdio( false ) ;
//	std::cin.tie( 0 ) ;
//	std::cout.tie( 0 ) ;
	return 0 ;
}