Problem Statement

There is a sequence called the Tetranacci sequence.
The Tetranacci sequence (denoted here by {$T_n$}) is defined as follows.
・$T_1 = 0,$ $T_2 = 0,$ $T_3 = 0,$ $T_4 = 1$
・$T_k = T_{k-1}$ $+$ $T_{k-2}$ $+$ $T_{k-3}$ $+$ $T_{k-4}$

Find the remainder when the $n_i$-th term $T_{n_i}$ of the Tetranacci sequence is divided by 17.

Input

$Q$
$n_1$
$n_2$

:

$n_Q$

The input consists of $Q+1$ lines.
The first line contains an integer $Q(1 \leq Q \leq 10^4)$, the number of queries.
Line $i+1(1 \leq i \leq Q)$ contains an integer $n_i(1 \leq n_i \leq 10^6)$.

Output

Output $Q$ lines.
On line $i(1 \leq i \leq Q)$, output the remainder when the $n_i$-th term $T_{n_i}$ of the Tetranacci sequence is divided by 17.
Add a newline at the end.

Sample

2
3
10

0
12

6
3
2
1
3
1
4

0
0
0
0
0
1

6
9
99
999
9999
99999
999999

15
12
2
16
4
14