Description

这道题是这样的：

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

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

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

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

求期望放出的能量。

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

Input Format

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

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

Output Format

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

1
2

1

Hint

样例解释

$\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}$$