1

#include<iostream>
#include<list>
#include<string>
using namespace std;

list<int> BigAddList(list<int> La,list<int> Lb )
{
list<int> Lc;
list<int> ::iterator it1,it2;
it1=La.begin();
it2=Lb.begin();

int carry=0;
while(it1!=La.end()||it2!=Lb.end())
{
int c=carry;
if(it1!=La.end())
{
c=c+(*it1);
it1++;
}
if(it2!=Lb.end())
{
c=c+(*it2);
it2++;
}
carry=c/10;
Lc.push_back(c%10);
}
if(carry>0) Lc.push_back(carry);
return Lc;
}

int main()
{
int o;
cin>>o;
for(int v=0;v<o;v++ )

{
list<int>La,Lb,Lc;

int T;
cin>>T;
for(int j=1;j<=T;j++)
{
if(j==1||j==2)
{
La.push_back(1);
Lb.push_back(1);
Lc.push_back(1);
}
else
{
Lc=BigAddList(La,Lb);
Lc.reverse();
}
La.swap(Lb);
Lb.swap(Lc);
}

for(list<int>::iterator it=Lc.begin();it!=Lc.end();it++)
{
cout<<*it;
}
cout<<endl;
}
}