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

void addBigNum(string& res, string a, string b){
    res = "";
    while (a.size() < b.size()) a = "0" + a;
    while (b.size() < a.size()) b = "0" + b;
    int cr = 0;
    for (int i = a.size()-1; i >= 0; i--){
        int t = a[i] + b[i] - 48*2 + cr;
        cr = t/10;
        t %= 10;
        res = (char)(t+48) + res;
    }
    if (cr) res = "1" + res;
}

const int maxn = 1e4 + 10;
string F[maxn];
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    F[0] = "1";
    F[1] = "1";
    for (int i = 2; i <= 5000; i++){
        addBigNum(F[i], F[i-1], F[i-2]);
    }
    int n;
    cin >> n;
    while (cin >> n) cout << F[n] << "\n";
}