import std.algorithm; import std.array; import std.conv; import std.math; import std.range; import std.stdio; import std.string; import std.typecons; T read(T)() { return readln.chomp.to!T; } T[] reads(T)() { return readln.split.to!(T[]); } alias readint = read!int; alias readints = reads!int; int calc(int n) { assert(n > 0); if (n <= 3) return 0; if (n == 4) return 1; auto m = new Mat4x4([[1, 1, 1, 1], [1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0]]); const mod = 17; auto ret = m.pow(n - 1, mod); return ret.get(3, 0); } void main() { int q = readint; for (int i = 0; i < q; i++) { int n = readint; int ans = calc(n); writeln(ans); } } class Mat4x4 { private const N = 4; private const int[][] _mat; this(const int[][] init) { assert(init.length == N); assert(init[0].length == init[1].length && init[0].length == N); _mat = init.dup; } int get(int r, int c) const { return _mat[r][c]; } Mat4x4 mul(const Mat4x4 m, int mod) const { auto t = new int[][](N, N); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { int x = 0; for (int k = 0; k < N; k++) { x = (x + (_mat[i][k] * m.get(k, j)) % mod) % mod; } t[i][j] = x; } } return new Mat4x4(t); } Mat4x4 copy() const { return new Mat4x4(_mat); } Mat4x4 pow(int k, int mod) const { assert(k > 0); if (k == 1) return this.copy(); auto m = this.pow(k / 2, mod); return k % 2 == 0 ? m.mul(m, mod) : this.mul(m.mul(m, mod), mod); } void dump() const { writeln(_mat[0][0], " ", _mat[0][1], " ", _mat[0][2], " ", _mat[0][3]); writeln(_mat[1][0], " ", _mat[1][1], " ", _mat[1][2], " ", _mat[1][3]); writeln(_mat[2][0], " ", _mat[2][1], " ", _mat[2][2], " ", _mat[2][3]); writeln(_mat[3][0], " ", _mat[3][1], " ", _mat[3][2], " ", _mat[3][3]); } }