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())]); } } }