该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

前一段时间，Ocean 最近在做矩阵题，发现他已经好久没有碰过斐波那契数列了。

于是，他便开始怀疑，你是否也已经忘记如何推导了，并定义了一个新数列，我们姑且叫他 奇怪的数列。

我们假设这里有一个奇怪的数列 $a$，那么定义这个数列如下：

1. 下标从 $1$ 开始；
2. $a_1 = 6, a_2 = 1, a_3 = 6$；
3. 对于 $i \geq 4$，有 $a_i = 61 \times a_{i - 1} + 11 \times a_{i - 2} + 16 \times a_{i - 3}$

很显然，当 $i$ 达到一定数量后，$a_i$ 会超出 $int$ 的范围，从而我们考虑对其取模。

现在，给你 $q$ 个询问，每次询问给你一个整数 $i$，请输出 $a_i$ 对 $998244353$ 取模后的值。

如果你不知道取模要怎么写，参阅题目最后的提示。

输入格式

第一行为一个整数 $q$，代表询问的次数。

接下来有 $q$ 行，每一行给定一个正整数 $i$，表示询问的下标。

输出格式

对于每一个询问，输出一行，每行包含一个整数，为 $a_i$ 对 $998244353$ 取模后的值。

样例

样例输入1

5
1
3
5
7
9

样例输出1

6
6
28935
108316227
193411864

说明1：数据范围

$1 \leq q, i \leq 2 \times 10 ^ 5$

说明2：取模操作

好心的 Ocean 打算教你取模，还不谢谢（?

首先，就像 $64 \div 3 = 21 \ldots 1$，我们在小学就知道了，这个 $1$ 就是余数。

那么，我们可以将上式改为 $64 \bmod 3 = 1$，即为 "64 除 3 后的余数是多少"。我们也可以用另一个表述方式，即："1 是 64 对 3 取模后的值"。

如果我们有一个式子，他是 $a = p \cdot x + q \cdot y + r \cdot z$，那么如果我们要求 $a \bmod M$ 的值，我们只需求 $(p \cdot x + q \cdot y + r \cdot z) \bmod M$ 的值即可。

因为 $(a \cdot b) \bmod M = ((a \bmod M) \cdot (b \bmod M)) \bmod M$（两数乘积取模 等于 两数分别取模后再相乘取模），所以我们只需求：

$((p \bmod M) \cdot (x \bmod M) + (q \bmod M) \cdot (y \bmod M) + (r \bmod M) \cdot (z \bmod M)) \bmod M$。

你学会了吗？