#include<bits/stdc++.h>
using namespace std;
#define int long long
int ans[3][3],a[3][3];
int t[3][3];
void jzcf(int x[3][3],int y[3][3])
{
	memset(t,0,sizeof(t));
	for (int i=0;i<=2;i++)
		for (int j=0;j<=2;j++)
			for (int k=0;k<=2;k++)
				t[i][j]=(x[i][k]*y[k][j]+t[i][j]);
	for (int i=0;i<=2;i++)
		for (int j=0;j<=2;j++)
			x[i][j]=t[i][j];
}

signed main()
{
	int t;
	cin>>t;
	while (t--)
	{
		int n;
		cin>>n;
		if (n<=3)
		{
			cout<<1<<endl;
			continue;
		}
		memset(ans,0,sizeof(ans));
		memset(a,0,sizeof(a));
		ans[0][0]=a[0][0]=1;ans[0][2]=a[0][2]=1;
		ans[1][0]=a[1][0]=1;ans[2][1]=a[2][1]=1;
		n--;
		while (n!=0)
		{
			if (n&1) jzcf(ans,a);
			jzcf(a,a);
			n>>=1;
		}
		cout<<ans[1][0]<<endl;;
	}
	return 0;
}