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 $n+1$ lines.
The first line contains an integer $Q(1 \leq Q \leq 10^4)$ representing the number of queries.
The $i+1(1 \leq i \leq Q)$-th line contains an integer $n_i(1 \leq n_i \leq 10^{18})$
.

Output

Output $Q$ lines.
On the $i(1 \leq i \leq Q)$-th line, 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

7
99
9999
999999
99999999
9999999999
999999999999
99999999999999

12
16
14
13
6
16
9