#include<bits/stdc++.h>
using namespace std;
const double pi=3.14;
const int inf=0x3f3f3f3f;
const int NIL=-1;
#define f(i,l,r) for(int i=l;i<=r;i++)
struct matrix{
	int mat[1001][1001];
	int matn,matm;
};
matrix operator*(const matrix &m1,const matrix &m2){
	matrix m3;
	m3.matn=m1.matn;
	m3.matm=m2.matm;
	for (int i=1;i<=m3.matn;i++){
		for (int j=1;j<=m3.matm;j++){
			for (int k=1;k<=m1.matn;k++){
				m3.mat[i][j]+=(m1.mat[i][k]*m2.mat[k][j]);
			}
		}
	}
	return m3;
}
matrix a,b;
void init(){
	
	memset(a.mat,0,sizeof(a.mat));
	a.mat[1][1]=a.mat[1][2]=a.mat[1][3]=1;
	a.matn=1;
	a.matm=3;
	memset(b.mat,0,sizeof(b.mat));
	b.mat[2][1]=b.mat[1][3]=b.mat[3][2]=b.mat[3][3]=1;
	b.matn=b.matm=3;
}
matrix pow(matrix p,int x)
{
	matrix ans=p;
	while(x)
	{
		if(x%2==1) ans=ans*p;
		p=p*p;
		x>>=1;
	}
	return ans;
}
int read()
{
    int ans=0,flag=1;
    char ch=getchar();
    while( (ch>'9' || ch<'0') && ch!='-' ) ch=getchar();
    if(ch=='-') flag=-1,ch=getchar();
    while(ch>='0' && ch<='9') ans=ans*10+ch-'0',ch=getchar();
    return ans*flag;
}
int main()
{
	cout<<"FU"<<endl; 
	init();
	int T;
	T=read();
	while(T--){
		int y=read();
		if (y<=3){
			cout<<1<<endl;
			continue;
		}
		else y-=3;
		b=pow(b,y-1);
		a=a*b;
		cout<<a.mat[1][1]<<endl;
	}
}

主函数中连第一行做备用的FU根本都不输出，正常运行不让输入