/***
 * Solution to Drones - CodeIT Season 6, Round 6, Problem J3
 * Author - Bozhidar Vasilev
**/

#include <iostream>
#include <fstream>

using namespace std;

const int MAX_N = 1000001;
unsigned long long T[MAX_N];
const unsigned long long MOD = -59;

void compute()
{
    T[0] = 1; T[1] = 1;
    for(int i = 2; i < MAX_N; ++i)
    {
        if(MOD - T[i-1] > T[i-2])
        {
            T[i] = T[i-1] + T[i-2];
        }
        else
        {
            unsigned long long m = MOD - T[i-1];
            T[i] = T[i-2] - m;
        }
    }
}

int main()
{
    freopen("drones.in", "r", stdin);
    freopen("drones.out", "w", stdout);
    compute();
    int q;
    cin >> q;
    while( q-- )
    {
        int n;
        cin >> n;
        cout << T[n] << endl;
    }
    return 0;
}