说明

时间限制：1 Sec 内存限制：256 MB 输入文件：fib.in 输出文件：fib.out

存在一类数列叫做四阶斐波那契数列，本题记为 $\{T_n\}$，定义如下：

- $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}\quad (k\ge5)$

对于每组询问，求四阶斐波那契数列第 $n_i$ 项 $T_{n_i}$ 模 $17$ 的余数。

输入格式

第一行一个整数 $Q$，代表询问次数。

接下来 $Q$ 行，每行一个整数 $n_i$。

输出格式

输出共 $Q$ 行，第 $i$ 行输出 $T_{n_i} \bmod 17$。每行末尾必须换行。

样例

样例 1

2
3
10

0
12

样例说明：

第 $3$ 项为 $0$；第 $10$ 项等于 $29$，$29 \bmod 17 = 12$。

样例 2

6
3
2
1
3
1
4

0
0
0
0
0
1

样例说明：

输入的数值不一定互不相同。

样例 3

7
99
9999
999999
99999999
9999999999
999999999999
99999999999999

12
16
14
13
6
16
9

样例说明：

输入数值可能超出 $32$ 位整数范围。

数据范围

对于 10% 的数据，$Q \le 100$，$n_i \le 10^6$。

对于 30% 的数据，$Q \le 1000$，$n_i \le 10^6$。

对于 40% 的数据，$n_i \le 10^6$。

对于 60% 的数据，$n_i \le 10^9$。

对于 100% 的数据，$1\le Q\le 10^4,\quad 1\le n_i \le 10^{18}$。