/**********************************************************
テトラナッチ数列のni番目の項Tniを17で
割った余りを求めるプログラム
入力:niの総数、テトラナッチ数列のni番目のni
出力:テトラナッチ数列のni番目の項Tniを17で割った余りをniの総数分
**********************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<inttypes.h>

int main(){

    long long int* data;    /* テトラナッチ数列のni番目のniをniの総数分だけ格納するポインタ */
    long long int* tetora;  /* テトラナッチ数列 */
    long long int i;    /* カウンタ */
    long long int n;    /* niの総数 */
    long long int max = -1; /* ポインタdataの中の最大値 */

    scanf("%"SCNd64"",&n); /* niの入力 */
    data = (long long int*)calloc((int)n,sizeof(long long int)); /* niの総数分領域確保 */

    /* ポインタdataに入力niを全て格納 */
    for(i=0; i<n; i++){
            scanf("%"SCNd64"",data+i);
            if( max < data[i] ) max = data[i];  /* 入力niの内、最大値を格納 */
    }

    tetora = (long long int*)calloc((int)max,sizeof(long long int)); /* 指定されたniの内、最大値分だけ領域確保 */

    /* テトラナッチ数列を求める */
    for(i=1; i<=max; i++){
        switch(i){  /* {Tn}を求めていく */
            case 1:
                tetora[i-1] = 0;    /* T1=0 */
                break;
            case 2:
                tetora[i-1] = 0;    /* T2=0 */
                break;
            case 3:
                tetora[i-1] = 0;    /* T3=0 */
                break;
            case 4:
                tetora[i-1] = 1;    /* T4=1 */
                break;
            default:
                tetora[i-1] = (tetora[i-2] + tetora[i-3] + tetora[i-4] + tetora[i-5])%17;   /* Tk = Tk−1 + Tk−2 + Tk−3 + Tk−4 */
                break;
        }
    }

    for(i=0; i<n; i++){
        printf("%lld\n",tetora[data[i]-1]); /* 出力 */
    }

    return 0;
}