定义回文串为正着反着都一样的串，例如ababa是回文串而abab不是。

定义一个字符串的划分为一些子序列的集合，使得这些子序列不重不漏的覆盖了整个串。

例如aaaba可以划分为{a,a,a,b,a},{aaa,ba},{aaaba},{aaaa,b},{ab,aaa}等。

对于一个字符串S，定义$f(S)$ 为最少划分出的子序列数，使得每个子序列都是回文串。

现在CZY对lk口胡了一个字符串S，要lk算出f(S)，但是lk这么菜当然不会，所以把这个问题丢给你。

但是由于lk记性比较差，把这个问题交给你的时候，他已经不记得这个串是啥了，他只记得这个串由n个字母组成，且每个字符仅可能是a或b。

所以丢给你的问题就变成了，对于任意一个可能的串S，计算$f(S)$的和。

输入格式

第一行一个数T，表示有T组数据。

接下来有T行，每行一个数n，表示串长为n。

输出格式

T行，每行一个数，表示$f(S)$的和。由于答案比较大，输出对998244353取膜。

输入输出样例

样例输入

2
1
2

样例输出

2
6

数据范围

测试点1，1分，T=0。

测试点2，24分，$n\le 10$。

测试点3，25分，$n\le 10^5$，$T\le 100$。

测试点4，50分，$n\le 10^{16}$，$T\le 10^6$。

时间限制每个点5秒。