暂无测试数据。

Darko 是一个喜欢数数的女孩子，她也喜欢听歌，比如这首《Brain Power》：

DarkO-oooooooooo AAAAE-A-A-I-A-U- JO-oooooooooooo AAE-O-A-A-U-U-A- E-eee-ee-eee AAAAE-A-E-I-E-A- JO-ooo-oo-oo-oo EEEEO-A-AAA-AAAA

Darko 在 Brain Power 下，奇怪的数数能力增加了！

给你 $T$ 组询问，每次给定一个正整数 $n$，求

• 一个 $4\times n$ 的方格，对每个格子黑白染色，任意同种颜色的四连通块大小不大于 $4$ 的方案数。

答案对 $998244353$ 取模。

对于所有数据，$T\leq 100$，$n\leq 10^{18}$。

输入格式

输入共 $T+1$ 行。

第 $1$ 行读入 $1$ 个正整数 $T$。

接下来 $T$ 行每行读入一个正整数 $n$ 表示一次询问。

输出格式

输出共 $T$ 行。

每行一个整数表示方案数对 $998244353$ 取模的结果。

数据规模与约定

对于 $10\%$ 的数据，满足 $T=5$，$n\leq 5$。

对于 $20\%$ 的数据，满足 $T\leq 10$，$n\leq 10$。

对于 $40\%$ 的数据，满足 $T\leq 10$，$n\leq 100$。

对于 $60\%$ 的数据，满足 $n\leq 10^5$。

对于另外 $20\%$ 的数据，满足 $T=1$。

对于所有数据，$T\leq 100$，$n\leq 10^{18}$。

5
2
3
10
1145141919810
3141592653589793

142
722
102352864
171943462
670785400