#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;
}