using System;

public class Hello
{
    public static void Main()
    {
        var a = new int[1000001];
        a[4] = 1; a[5] = 1;
        tetraset(a);
        var q = int.Parse(Console.ReadLine().Trim());
        for (int i = 0; i < q; i++)
        {
            var n = int.Parse(Console.ReadLine().Trim());
            Console.WriteLine(a[n]);
        }
    }
    public static void tetraset ( int[] a )
    {
        for (int i = 6; i <= 1000000; i++)
            a[i] = (a[i - 1] + a[i - 2] + a[i - 3] + a[i - 4]) % 17;
    }
}