import java.util.*;
import java.util.stream.*;
class Main {
    static Scanner s=new Scanner(System.in);
    static int gInt(){return Integer.parseInt(s.next());}
    public static void main(String[]$){
        int[]a=new int[1000000];
        a[3]=1;
        for(int i=4;i<1000000;++i)
            a[i]=(a[i-1]+a[i-2]+a[i-3]+a[i-4])%17;
        for(int q=gInt();q>0;--q)
            System.out.println(a[gInt()-1]);
    }
}