#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <queue>
#include <math.h>

using namespace std;

int main()
{
	freopen( "drones.in", "r", stdin );
    freopen( "drones.out", "w", stdout );
    int bk;
    cin>>bk;
    int kol;
    queue<int>ans;
    unsigned long long mod=2;
    for(int i=1;i<64;i++)
    {
    	mod*=2;
	}
    unsigned long long seg=1,pred=1,op=1;
    for(int i=0;i<bk;i++)
    {
    	cin>>kol;
		//ans.push(fib(kol));
		for(int i=1;i<kol;i++)
		{
			op=pred;
			pred=seg;
			seg=(pred+op)%(mod-59);
		}
		ans.push(seg);
		seg=1;
		pred=1;
		op=1;
	}
	while(!ans.empty())
	{
		cout<<ans.front()<<endl;
		ans.pop();
	}
}