在长度为 $N$、由大小写英文字母组成的字符串中，求出同时包含“NPCAPC”和“npcapc”作为子序列（不一定连续）的字符串数量，结果对 998244353 取模。

你需要解决 $T$ 组测试用例。

数据范围

• $1 \le T \le 5000$
• $1 \le N \le 10^9$

输入格式

输入通过标准输入按以下格式给出：

$T$ $case_1$ $case_2$ $\vdots$ $case_T$

其中 $case_i$ 表示第 $i$ 组测试用例。每个测试用例的格式如下：

$N$

输出格式

输出 $T$ 行。第 $i$ 行输出第 $i$ 组测试用例的答案。

样例

输入格式 1

4
12
6
5839
123456

输出格式 1

924
0
966252995
432934749

说明

对于第一个样例： 在第一个测试用例中，共有 924 个字符串满足条件，例如 ‘npcapcNPCAPC’ 和 ‘NPCnpcAapPCc’。

输入格式 2

3
123456789
987654321
999999999

输出格式 2

333574957
124462731
163251704