// https://dashoj.com/p/129
#include <bits/stdc++.h>

using namespace std;

int main() {
	int n;
	cin >> n;
	while (n--) {
		int m;
		cin >> m;
		vector<int> dp(m + 7, 0);
		dp[1] = 1, dp[2] = 1;
		for (int i = 4; i <= m; i++) dp[i] += dp[i - 1] + dp[i - 2];
		cout << dp[m] << endl;
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;

int dp[45]; 
int m; // m 级楼梯
int n; // 测试数据的个数

// 初始化dp数组，计算1-40级台阶
void InitDp()
{
    dp[1] = 1; // 走上一级台阶只有一种走法
    dp[2] = 2; // 走上两级台阶只有两种走法
    // 后面的台阶既有可能是跨一级到的，也有可能是通过跨两级到的。因此状态转移方程是a[m]=a[m-1]+a[m-2]
    for(int i = 3; i <= 40; i++)
    {
        dp[i] = dp[i-1]+dp[i-2];
    }
}

int main()
{
    InitDp();
    cin >> n;
    while(n--)
    {
        cin >> m;
        cout << dp[m-1] << endl; // 题上说的是走上m级,所以要走的有m-1级
    }

    return 0;
}

#include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int>su(n+1); for (int i = 1; i <= n; i++)cin >> su[i]; int way[1001]; way[1] = 0; way[2] = 1; way[3] = 2; for (int i = 1; i <= n; i++) { for (int j = 4; j <= su[i]; j++) way[j] = way[j - 1] + way[j - 2]; cout << way[su[i]] << endl; }

return 0;

}

#include <bits/stdc++.h>
using namespace std;
int dp[N]={0};
signed main(){
	int count;
	dp[1]=1;
	dp[2]=1;
	cin>>count;
	
	for(int i=3;i<51;i++){
		dp[i]=dp[i-1]+dp[i-2];
	}
	for(int i=0;i<count;i++){
		int x;
		cin>>x;
		cout<<dp[x]<<endl;
	}

	return 0;
}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n=sc.nextInt();  //次数为n
        int[] m=new int[n];

        for (int i = 0; i < n; i++) {
            m[i]=sc.nextInt()-1;
        }
        int[][] dp=new int [n][45];

        for (int i = 0; i < n; i++) {
            dp[i][0]=1;
            dp[i][1]=1;
            dp[i][2]=2;
        }


        for (int i = 0; i < n; i++) { //次数
            for (int j = 2; j <= m[i]; j++) {  //
                dp[i][j]=dp[i][j-1]+dp[i][j-2];
            }
        }

        for (int i = 0; i < n; i++) {
            System.out.println(dp[i][m[i]]);
        }
    }
}

for i in range(int(input())):
    m = int(input())
    dp = [0]*50
    dp[1] =1 
    dp[2] =1 
    for i in range(3,45):
        dp[i] = dp[i-1]+dp[i-2]
        
    print(dp[m])