题目背景

“呐，珈百璃，我说，暑假我们去哪里玩呢？”薇奈特拍拍珈百璃的肩膀

“哈？暑假当然是在家里打游戏啦”珈百璃无精打采地回答道

“怎么能这样呢？你好歹也是天使啊，给我拿出天使的样子来啊”

“真麻烦”

“所以，暑假我们去海边玩吧？”

“赞成赞成！去海边玩的话，就可以好好调戏珈百璃了”菈菲尔不知道什么时候凑进来

“麻烦死了。”

这边一群人正讨论着暑假去哪玩，然而萨塔尼亚在旁边听得很纠结，因为没有人邀请她。。

“哼哼哼哼，吾乃神魔萨塔尼亚，怎么可能主动去加入呢，我必须等她们邀请我”萨塔尼亚心理打着小算盘

“呐，我说，萨塔尼亚貌似有点小不开心呀”

“已经不是貌似了吧，她这表情完全没有掩盖的意思啊。。”

“呐，我说，要不要邀请她去啊？”

拉菲尓说着，走向了萨塔尼亚。“萨塔尼亚桑，暑假我们要去海边玩哟~”

“哼哼哼，终于来邀请我了吗”萨塔尼亚心里有点小开心，小声嘀咕到

“萨塔尼亚桑就好好待在这里哟~”

“额。。。”萨塔尼亚受到了成吨的暴击，“喂，我说，哪有你这样的啊”

“恩？因为，萨塔尼亚桑，暑假如果要出去玩的话，就要通过期末考试哟，不然会被留下来补课的”

“补。。。补课。。。。”萨塔尼亚貌似意会到了什么，脸色大变，“补课。。。呐，拉菲尓。。你。。你能帮我。。补习吗？”

“恩？可以呀~但是期末考试如何就得看你自己了”

“谢谢，那帮我看看这些哪里错了吧？我完全不懂诶”

“我看看。。。” 拉菲尓丢下珈百璃和薇奈特独自给萨塔尼亚开始了补习。

终于，期末考来了，萨塔尼亚努力的这么久，就看这次考试了！经过长期的努力，期末考一切顺利，除了还没考的数学其他学科都及格啦！

终于到了最后一场考试——物理考试。很不错的是，萨塔尼亚已经答完了59分而且全对，但是她遇到了一道绝世难题，而且她很惊奇的发现，总分100分，这题41分，如果不写出来，就会挂科。“期末考如果有某人有挂科，那么那个人的暑假要参加补课以及补考！”班主任的话萦绕在她的耳旁，这可怎么办啊。。。

题目描述

这道题是这样的：

有一个由 $n$ 个点电荷形成的电场。假定每个点电荷放出的电场都是匀强电场而不是点电荷电场，第 $i$ 个点电荷的电场强度 $E_i=i$。

现放一个带负电的试探电荷到这个电场中，这个试探电荷只要触碰到任何一个点电荷就会和这个点电荷发生聚变放出巨大能量。

因为点电荷放出的电场强度不同，所以试探电荷被吸引到每个点电荷的概率也不同，点电荷给试探电荷的吸引力越大被吸到这个点电荷的概率就越大，且成正比。

我们假设最小的点电荷给试探电荷的吸引力为 $F$，那么对于其他点电荷给试探电荷和吸引力就是 $iF$，那么假设触碰最小的点电荷的概率为 $P$，则每个点的概率就是 $iP$，触碰到点电荷后发出的能量为 $\mathrm{Fib}(E_i)$。

求期望放出的能量。

好消息是，只要这道题拿到分，萨塔尼亚就能及格啦！

输入格式

第一行一个整数 $T$，表示共有 $T$ 组测试数据。

接下来 $T$ 行每行一个整数 $n$，表示有 $n$ 个点电荷。

输出格式

对于每次询问输出一行一个整数表示期望能量。为了避免精度问题，请输出答案对 $998{,}244{,}353$ 取模后的结果。

1
2

1

提示

样例解释

$\dfrac{1}{3}\times \mathrm{Fib}(1)+\dfrac{2}{3}\times \mathrm{Fib}(2)=1$。

请结合样例仔细再仔细的读题！

数据范围

• 对于 $10\%$ 的数据 $T=1$，$n=2$；
• 对于 $30\%$ 的数据 $T≤10$，$1\le n\le 10^6$；
• 对于 $60\%$ 的数据 $T≤10^6$，$1\le n\le 10^6$；
• 对于 $100\%$ 的数据 $T≤10^6$，$1\le n\le 10^9$，保证 $n \ne 998244352$ 且 $n \ne 998244353$。

$\mathrm{Fib}(i)$ 为斐波那契数列。

$$\mathrm{Fib}(i)=\begin{cases} 1 & i\le 2 \cr \mathrm{Fib}(i-1)+\mathrm{Fib}(i-2) & i > 2 \end{cases}$$