U149068 这次是四阶

 Miku 穿着可爱的袜子，拎着可爱的袋子，还在可爱地思考数学问题呢。 现在，她又有了一个数列呢。

定义数列 $a$，满足 $$a_i = \begin{cases} 6 & (i = 1)\\ 3 & (i = 2)\\ 5 & (i = 3)\\ 8 & (i = 4)\\ a_{i-4} + a_{i-1} - 7 & (i > 4,\ i\equiv1\pmod{2})\\ a_{i-4} + a_{i-1} + 1 & (i > 4,\ i\equiv0\pmod{2}) \end{cases}$$ 给定一个正整数 $k$，请你求出 $a_k$ 的值，对 $998\,244\,353$ 取模。

第 $1$ 行：一个正整数 $T$，表示数据组数。 接下来 $T$ 行：每行一个正整数 $k_i$，表示计算 $a_{k_i}$ 的值。

共 $T$ 行，第 $i$ 行为 $a_{k_i}$ 的值对 $998\,244\,353$ 取模后的结果。

#### 数据规模与约定 对于 $10\%$ 的数据，是样例。 对于 $100\%$ 的数据，$k_i \leq 10^{16},\ T \leq 10^3$. 样例及测试点 #10 的数据手工生成，其余测试点数据均为随机。 #### 提示 注意最终输出的结果一定要非负哦！