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

I2luY2x1ZGUgImJpdHMvc3RkYysrLmgiCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp2b2lkIGFkZEJpZ051bShzdHJpbmcmIHJlcywgc3RyaW5nIGEsIHN0cmluZyBiKXsKICAgIHJlcyA9ICIiOwogICAgd2hpbGUgKGEuc2l6ZSgpIDwgYi5zaXplKCkpIGEgPSAiMCIgKyBhOwogICAgd2hpbGUgKGIuc2l6ZSgpIDwgYS5zaXplKCkpIGIgPSAiMCIgKyBiOwogICAgaW50IGNyID0gMDsKICAgIGZvciAoaW50IGkgPSBhLnNpemUoKS0xOyBpID49IDA7IGktLSl7CiAgICAgICAgaW50IHQgPSBhW2ldICsgYltpXSAtIDQ4KjIgKyBjcjsKICAgICAgICBjciA9IHQvMTA7CiAgICAgICAgdCAlPSAxMDsKICAgICAgICByZXMgPSAoY2hhcikodCs0OCkgKyByZXM7CiAgICB9CiAgICBpZiAoY3IpIHJlcyA9ICIxIiArIHJlczsKfQoKY29uc3QgaW50IG1heG4gPSAxZTQgKyAxMDsKc3RyaW5nIEZbbWF4bl07CnNpZ25lZCBtYWluKCl7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUoMCk7CiAgICAKICAgIEZbMF0gPSAiMSI7CiAgICBGWzFdID0gIjEiOwogICAgZm9yIChpbnQgaSA9IDI7IGkgPD0gNTAwMDsgaSsrKXsKICAgICAgICBhZGRCaWdOdW0oRltpXSwgRltpLTFdLCBGW2ktMl0pOwogICAgfQogICAgaW50IG47CiAgICBjaW4gPj4gbjsKICAgIHdoaWxlIChjaW4gPj4gbikgY291dCA8PCBGW25dIDw8ICJcbiI7Cn0=

MQoxMDAwMA==

1
10000