题目描述

easy 和 hard 版本的不同仅仅在数据范围上！！！

小 H 在做数学题时发现了两个有趣的递推式 $f_n,g_n$，但是他在计算第 $n$ 项的时候感到很困难，因为递推是计算机做的事情，现在只有你有一台计算机，请帮帮他计算计算，小 H 觉得答案肯定很大，所以他只想知道答案对 $998244353$ 取模后的结果。两个递推式如下：

$$f_n= \begin{cases} 1,&\text{$n$ = 1}\\ 2,&\text{$n$ = 2}\\ 2f_{n-1}+3f_{n-2}+n,&\text{$n \ge$ 3}\\ \end{cases} \\ g_n= \begin{cases} 2,&\text{$n$ = 1}\\ g_{n-1}+f_n+n^2,&\text{$n \ge$ 2}\\ \end{cases} $$

你只需要告诉小 H $g_n$ 对 $998244353$ 取模后的值就行了。

输入格式

第一行一个正整数 $T$（$1\le T \le 10^4$），代表 $T$ 组测试样例。

每个测试样例有一个正整数 $n$（$1\le n \le 10^9$），表示需要求出的项数。

输出格式

输出 $T$ 行，每行一个正整数表示答案对 $998244353$ 取模后的结果。

样例输入

6
1
2
3
4
5
456

样例输出

2
8
27
73
193
346431351

样例解释

当 $1\le n\le 5$ 时，$f_i,g_i$ 对应的值如下：

$$\begin{array}{c|cccc} \text{$i$}&1&2&3&4&5\\ \hline f_i&1&2&10&30&95\\ g_i&2&8&27&73&193\\ \end{array} $$