#include <iostream>
#include <string>
#include <algorithm>
#define ll long long
using namespace std;
string ans[101];
string addStrings(string num1, string num2) {
while(num1.size()>num2.size())
{
num2='0'+num2;
}
while(num2.size()>num1.size())
{
num1='0'+num1;
}
int n=num2.size();
int res;
string ans="";
int carry=0;
for(int i=n-1;i>=0;i--){
res=((num1[i]-'0')+(num2[i]-'0')+carry)%10;
carry=((num1[i]-'0')+(num2[i]-'0')+carry)/10;
ans=ans+ to_string(res);
}
if(carry==1){ ans=ans+to_string(1);}
reverse(ans.begin(),ans.end());
return ans;
}
void solve()
{
int n;
cin >> n;
cout << ans[n] << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ans[0]='1', ans[1] = '1';
for (int i=2; i<101; ++i)
{
ans[i] = addStrings(ans[i-1], ans[i-2]);
}
int tc;
cin >> tc;
while (tc--)
{
solve();
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojZGVmaW5lIGxsIGxvbmcgbG9uZwp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RyaW5nIGFuc1sxMDFdOwoKc3RyaW5nIGFkZFN0cmluZ3Moc3RyaW5nIG51bTEsIHN0cmluZyBudW0yKSB7CiAgICAKICAgICAgICB3aGlsZShudW0xLnNpemUoKT5udW0yLnNpemUoKSkKICAgICAgICB7CiAgICAgICAgICAgIG51bTI9JzAnK251bTI7CiAgICAgICAgfQogICAgICAgIHdoaWxlKG51bTIuc2l6ZSgpPm51bTEuc2l6ZSgpKQogICAgICAgIHsKICAgICAgICAgICAgbnVtMT0nMCcrbnVtMTsKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgaW50IG49bnVtMi5zaXplKCk7CiAgICAgICAgaW50IHJlczsKICAgICAgICBzdHJpbmcgYW5zPSIiOwogICAgICAgIGludCBjYXJyeT0wOwogICAgICAgZm9yKGludCBpPW4tMTtpPj0wO2ktLSl7CiAgICAgICAgICAgcmVzPSgobnVtMVtpXS0nMCcpKyhudW0yW2ldLScwJykrY2FycnkpJTEwOwogICAgICAgICAgIGNhcnJ5PSgobnVtMVtpXS0nMCcpKyhudW0yW2ldLScwJykrY2FycnkpLzEwOwogICAgICAgICAgIGFucz1hbnMrIHRvX3N0cmluZyhyZXMpOwogICAgICAgICAgIAogICAgICAgfQogICAgICAgIGlmKGNhcnJ5PT0xKXsgYW5zPWFucyt0b19zdHJpbmcoMSk7fQogICAgICAgIHJldmVyc2UoYW5zLmJlZ2luKCksYW5zLmVuZCgpKTsKICAgICAgICByZXR1cm4gYW5zOwogICAgfQoKdm9pZCBzb2x2ZSgpCnsKICAgIGludCBuOwogICAgY2luID4+IG47CiAgICBjb3V0IDw8IGFuc1tuXSA8PCBlbmRsOwp9CgppbnQgbWFpbigpIHsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgY2luLnRpZShOVUxMKTsKICAgIAogICAgYW5zWzBdPScxJywgYW5zWzFdID0gJzEnOwogICAgZm9yIChpbnQgaT0yOyBpPDEwMTsgKytpKQogICAgewogICAgICAgIGFuc1tpXSA9IGFkZFN0cmluZ3MoYW5zW2ktMV0sIGFuc1tpLTJdKTsKICAgIH0KICAgIAogICAgaW50IHRjOwogICAgY2luID4+IHRjOwogICAgd2hpbGUgKHRjLS0pCiAgICB7CiAgICAgICAgc29sdmUoKTsKICAgIH0KICAgIAogICAgCiAgICByZXR1cm4gMDsKfQ==