問題文

テトラナッチ数列というものがある。
テトラナッチ数列（ここでは{$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}$

テトラナッチ数列の$n_i$番目の項$T_{n_i}$を17で割った余りを求めなさい。

入力

$Q$
$n_1$
$n_2$

:

$n_Q$

入力は$Q+1$行与えられ、
1行目にはクエリの回数を表す整数$Q(1\le Q\le {10}^4)$、
$i+1(1\le i\le Q)$行目には整数$n_i(1\le n_i\le {10}^6)$
が与えられる。

出力

$Q$行出力し、
$i(1\le i\le Q)$行目にはテトラナッチ数列の$n_i$番目の項$T_{n_i}$を17で割った余りを出力せよ。
末尾に改行を入れること。

サンプル

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