#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define mp make_pair
#define all(v) v.begin(),v.end()
#define int long long
#define ll long long
//#define M 1000000007
#define mii map<ll ,ll >
#define msi map<string,ll >
#define mis map<ll int, string>
#define rep(a,b) for(ll i=a;i<b;i++)
#define rep0(n) for(ll i=0;i<n;i++)
#define repi(i,a,b) for(ll i=a;i<b;i++)
#define pb push_back
#define vi vector<ll>
#define mp make_pair
#define vs vector<string>
#define ppb pop_back
#define endl '\n'
#define asdf ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define r0 return 0;
#define FORD(i, a, b) for (int i = (int) (a); i >= (int) (b); --i)
#define FORE(it, c) for (__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
#define inputoutput freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define input freopen("input.txt", "r", stdin);
#define Set(a, s) 4(a, s, sizeof (a))
#define FOR repi
//#define float long double
ll max(ll a, ll b) { return (a > b)? a : b;}
int min(int a, int b) { return (a < b)? a : b;}
void multiply(int a[2][2], int b[2][2])
{
// Creating an auxiliary matrix to store elements
// of the multiplication matrix
int mul[2][2];
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 2; j++)
{
mul[i][j] = 0;
for (int k = 0; k < 2; k++)
mul[i][j] += a[i][k]*b[k][j];
}
}
// storing the muliplication resul in a[][]
for (int i=0; i<2; i++)
for (int j=0; j<2; j++)
a[i][j] = mul[i][j]; // Updating our matrix
}
// Function to compute F raise to power n-2.
int power(int F[2][2], int n)
{
int M[2][2] = {{1,1},{1,0}};
// Multiply it with initial values i.e with
// F(0) = 0, F(1) = 1, F(2) = 1
if (n==1)
return F[0][0] + F[0][1];//+F[1][0]+F[1][1];
power(F, n/2);
multiply(F, F);
if (n%2 != 0)
multiply(F, M);
// Multiply it with initial values i.e with
// F(0) = 0, F(1) = 1, F(2) = 1
return F[0][0] + F[0][1];//+F[1][0]+F[1][1];
}
int solve()
{
int n;
cin>>n;
int F[2][2] = {{1,1},{1,0}};
//n--;
//if(n==0) cout<<2;
//else
cout<<power(F,n);
}
signed main()
{
asdf
int t=1;
cin>>t;
while(t--)
{
solve();cout<<endl;
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiAgICB1c2luZyBuYW1lc3BhY2Ugc3RkOwogICAgI2RlZmluZSBmZiBmaXJzdAogICAgI2RlZmluZSBzcyBzZWNvbmQKICAgICNkZWZpbmUgbXAgbWFrZV9wYWlyCiAgICAjZGVmaW5lIGFsbCh2KSB2LmJlZ2luKCksdi5lbmQoKQogICAgI2RlZmluZSBpbnQgbG9uZyBsb25nCiAgICAjZGVmaW5lIGxsIGxvbmcgbG9uZwogICAgLy8jZGVmaW5lIE0gMTAwMDAwMDAwNwoKICAgICNkZWZpbmUgbWlpICBtYXA8bGwgLGxsID4KICAgICNkZWZpbmUgbXNpICBtYXA8c3RyaW5nLGxsID4KICAgICNkZWZpbmUgbWlzICBtYXA8bGwgaW50LCBzdHJpbmc+CiAgICAjZGVmaW5lIHJlcChhLGIpICAgIGZvcihsbCBpPWE7aTxiO2krKykKICAgICNkZWZpbmUgcmVwMChuKSAgICBmb3IobGwgaT0wO2k8bjtpKyspCiAgICAjZGVmaW5lIHJlcGkoaSxhLGIpIGZvcihsbCBpPWE7aTxiO2krKykKICAgICNkZWZpbmUgcGIgcHVzaF9iYWNrCiAgICAjZGVmaW5lIHZpIHZlY3RvcjxsbD4KICAgICNkZWZpbmUgbXAgbWFrZV9wYWlyCiAgICAjZGVmaW5lIHZzIHZlY3RvcjxzdHJpbmc+CiAgICAjZGVmaW5lIHBwYiBwb3BfYmFjawogICAgI2RlZmluZSBlbmRsICdcbicKICAgICNkZWZpbmUgYXNkZiBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTtjaW4udGllKDApO2NvdXQudGllKDApOwogICAgI2RlZmluZSByMCByZXR1cm4gMDsKICAgICNkZWZpbmUgRk9SRChpLCBhLCBiKSBmb3IgKGludCBpID0gKGludCkgKGEpOyBpID49IChpbnQpIChiKTsgLS1pKQogICAgI2RlZmluZSBGT1JFKGl0LCBjKSBmb3IgKF9fdHlwZW9mKChjKS5iZWdpbigpKSBpdCA9IChjKS5iZWdpbigpOyBpdCAhPSAoYykuZW5kKCk7ICsraXQpCiAgICAjZGVmaW5lIGlucHV0b3V0cHV0IGZyZW9wZW4oImlucHV0LnR4dCIsICJyIiwgc3RkaW4pO2ZyZW9wZW4oIm91dHB1dC50eHQiLCAidyIsIHN0ZG91dCk7CiAgICAjZGVmaW5lIGlucHV0IGZyZW9wZW4oImlucHV0LnR4dCIsICJyIiwgc3RkaW4pOwogICAgI2RlZmluZSBTZXQoYSwgcykgNChhLCBzLCBzaXplb2YgKGEpKQogICAgI2RlZmluZSBGT1IgcmVwaQogICAgLy8jZGVmaW5lIGZsb2F0IGxvbmcgZG91YmxlCiAgICBsbCBtYXgobGwgYSwgbGwgYikgeyByZXR1cm4gKGEgPiBiKT8gYSA6IGI7fQogICAgaW50IG1pbihpbnQgYSwgaW50IGIpIHsgcmV0dXJuIChhIDwgYik/IGEgOiBiO30KCiAgICAKICAgIHZvaWQgbXVsdGlwbHkoaW50IGFbMl1bMl0sIGludCBiWzJdWzJdKSAKeyAKICAgIC8vIENyZWF0aW5nIGFuIGF1eGlsaWFyeSBtYXRyaXggdG8gc3RvcmUgZWxlbWVudHMgIAogICAgLy8gb2YgdGhlIG11bHRpcGxpY2F0aW9uIG1hdHJpeCAKICAgIGludCBtdWxbMl1bMl07IAogICAgZm9yIChpbnQgaSA9IDA7IGkgPCAyOyBpKyspIAogICAgeyAKICAgICAgICBmb3IgKGludCBqID0gMDsgaiA8IDI7IGorKykgCiAgICAgICAgeyAKICAgICAgICAgICAgbXVsW2ldW2pdID0gMDsgCiAgICAgICAgICAgIGZvciAoaW50IGsgPSAwOyBrIDwgMjsgaysrKSAKICAgICAgICAgICAgICAgIG11bFtpXVtqXSArPSBhW2ldW2tdKmJba11bal07IAogICAgICAgIH0gCiAgICB9IAogIAogICAgLy8gc3RvcmluZyB0aGUgbXVsaXBsaWNhdGlvbiByZXN1bCBpbiBhW11bXSAKICAgIGZvciAoaW50IGk9MDsgaTwyOyBpKyspIAogICAgICAgIGZvciAoaW50IGo9MDsgajwyOyBqKyspIAogICAgICAgICAgICBhW2ldW2pdID0gbXVsW2ldW2pdOyAgLy8gVXBkYXRpbmcgb3VyIG1hdHJpeCAKfSAKICAKLy8gRnVuY3Rpb24gdG8gY29tcHV0ZSBGIHJhaXNlIHRvIHBvd2VyIG4tMi4gCmludCBwb3dlcihpbnQgRlsyXVsyXSwgaW50IG4pIAp7IAogICAgaW50IE1bMl1bMl0gPSB7ezEsMX0sezEsMH19OyAKICAKICAgIC8vIE11bHRpcGx5IGl0IHdpdGggaW5pdGlhbCB2YWx1ZXMgaS5lIHdpdGggCiAgICAvLyBGKDApID0gMCwgRigxKSA9IDEsIEYoMikgPSAxIAogICAgaWYgKG49PTEpIAogICAgICAgIHJldHVybiBGWzBdWzBdICsgRlswXVsxXTsvLytGWzFdWzBdK0ZbMV1bMV07IAogIAogICAgcG93ZXIoRiwgbi8yKTsgCiAgCiAgICBtdWx0aXBseShGLCBGKTsgCiAgCiAgICBpZiAobiUyICE9IDApIAogICAgICAgIG11bHRpcGx5KEYsIE0pOyAKICAKICAgIC8vIE11bHRpcGx5IGl0IHdpdGggaW5pdGlhbCB2YWx1ZXMgaS5lIHdpdGggCiAgICAvLyBGKDApID0gMCwgRigxKSA9IDEsIEYoMikgPSAxIAogICAgcmV0dXJuIEZbMF1bMF0gKyBGWzBdWzFdOy8vK0ZbMV1bMF0rRlsxXVsxXTsgCn0gCgoKCgoKCgogICAgIGludCBzb2x2ZSgpCiAgICAgewogICAgICAgICBpbnQgbjsKICAgICAgICAgY2luPj5uOwogICAgICAgICBpbnQgRlsyXVsyXSA9IHt7MSwxfSx7MSwwfX07IAogICAgICAgICAvL24tLTsKICAgICAgICAgLy9pZihuPT0wKSBjb3V0PDwyOyAKICAgICAgICAgLy9lbHNlCiAgICAgICAgIGNvdXQ8PHBvd2VyKEYsbik7CgogICAgIH0KICAgIHNpZ25lZCBtYWluKCkKICAgIHsgICAKICAgICAgICBhc2RmCiAgICAgICAgaW50IHQ9MTsKICAgICAgICBjaW4+PnQ7CiAgICAgICAgd2hpbGUodC0tKQogICAgICAgIHsKICAgICAgICAgICAgc29sdmUoKTtjb3V0PDxlbmRsOwogICAgICAgIH0gICAgIAogICAgICAgIAp9