using System;

namespace _657
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] ret = new int[1000010];
            ret[1] = 0; ret[2] = 0; ret[3] = 0; ret[4] = 1;
            for (int i = 5; i < 1000010; i++) ret[i] = (ret[i - 1] + ret[i - 2] + ret[i - 3] + ret[i - 4]) % 17;
            int n = int.Parse(Console.ReadLine());
            for (int i = 0; i < n; i++) Console.WriteLine(ret[int.Parse(Console.ReadLine())]);
        }
    }
}