T521887 ⟦公开-Div.3⟧ 挖三填一 minecraft

Ryzen 是一个 [MC](https://pan.baidu.com/s/1zoM7K2cpj7bdyLee_VG1SA?pwd=1145) 老玩家。 [宣：我的世界启动器（Hello! Minecraft）](https://pan.baidu.com/s/1zoM7K2cpj7bdyLee_VG1SA?pwd=1145)

众所周知，[MC](https://pan.baidu.com/s/1zoM7K2cpj7bdyLee_VG1SA?pwd=1145) 的过夜方式有两种： + 1.挖三填一（建议早期缺乏物资时使用） + 2.用床跳过夜晚（建议有一定物资的人使用） 因为第一种方法可能生成[幻翼](https://zh.minecraft.wiki/w/%E5%B9%BB%E7%BF%BC?variant=zh-cn)，所以不能连续使用三次。\ Ryzen 要在 MC 里游玩 $N$ 天，他想知道有多少种过夜方式（答案对 $998244353^{100000}$ 取模）。

一行一个正整数 $t$。\ 接下来 $t$ 行，每一行一个整数 $N$。

$t$ 行，每一行个整数，代表方案总数。对 $998244353^{100000}$ 取模。

对于所有数据，$1 \le t \le 100$，$1 \le N \le 10^{18}$。