Migrated from Lutece 3159 SKP Loves Palindrome

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

SKP 喜欢打算法竞赛。有一天，她要去参加一个四星级编程大赛。她发现这一比赛名字居然是个回文串（Palindrome）。不仅如此，她还发现这个比赛名称的所有子串也是回文串。

SKP 对于这一类字符串产生了兴趣。她想知道，对于所有长度为 $n$ 且只由大写英文字母组成的字符串中，满足其所有子串都是回文串的有多少种？她觉得这个问题很难，所以让你来解决，你能帮帮她吗？

下面是SKP在网络上找到的一些定义：

* 回文串：正着读和反着读一样的字符串，如 $\mathtt{A}$，$\mathtt{BB}$，$\mathtt{YTY}$，$\mathtt{IOOI}$， $\mathtt{SKPKS}$，$\mathtt{CCPCC}$，$\mathtt{RACECAR}$ 是回文串，而 $\mathtt{SKP}$ 不是。

* 子串：我们称一个字符串 $S$ 是 $T$ 的子串当且仅当从 $T$ 的头部和尾部去掉若干个（可以是 $0$ 个）字符后可以得到 $S$。如 $\mathtt{SKP}$、$\mathtt{AKWF}$、$\mathtt{KPAKW}$、$\mathtt{SKPAKWF}$ 都是字符串 $\mathtt{SKPAKWF}$ 的子串，而 $\mathtt{SKK}$ 、 $\mathtt{PAF}$ 不是。

Input

输入数据的第一行包含一个整数 $T$，表示数据组数。

对于每一组数据，包括一行一个整数 $n$，表示询问的字符串长度。

Output

对于每一组输入，输出对于长度为 $n$ 的字符串且满足限制的字符串的数量。由于答案可能很大，你只需要输出答案对 $998255343$ 取模后的结果即可。

Samples

2
1
2

26
26

Constraints

$1\le T\le 10^5$

$1\le n\lt 998255343$