U198916 [小翔系列水题] 蒜头2
题目背景
小翔在大师的帮助下发现了好多颗蒜头。
题目描述
蒜头的侧面被分成了 $N$ 块（ $N > 2$ ），且每一块完全相同。蒜头的 $N$ 块的编号分别为 $0, 1, 2, 3, ..., N-1$ 。为了帮助你理解，小翔给了你一个被分成 $4$ 块的蒜头，如果它的侧面表皮被剥下来平铺在桌面上，那么将是如下的样子：
其中，编号相差为 $1$ 的两个块是相邻的。特别地， $0$ 号块和 $N-1$ 号块也是相邻的（图中 $0$ 和 $3$ 相邻）。
你在小翔的帮助下成功理解了蒜头的构造。现在小翔又犯病了，他想用黑笔给某些块染上**黑色**，同时他又不希望两个挨着的块都是黑色的。他可以任意染任意多的色。蒜头可以**水平**旋转，**旋转后重合的方案视为一种方案**。他现在想知道有几种不同的涂法（模 $998244353$ ）。
注意：全部不涂也是一种方案。
输入格式
第一行输入一个正整数 $T$ ，表示蒜头数量。
接下来每行输入一个正整数 $N$ ，表示蒜头被分成的块数。
输出格式
输出 $T$ 行，每行一个正整数，表示第 $i$ 个蒜头的答案在模 $998244353$ 意义下的值。
说明/提示
### 样例解释：
对于第一个蒜头，可以涂一个，可以不涂，总共两种方案。
例如：涂 $0$ 号，或者不涂。可以发现涂 $1$ 号和涂 $0$ 号本质相同且没有其他使黑块不相邻的方案。
对于第二个蒜头，可以涂一个，可以不涂，总共两种方案。
例如：涂 $0$ 号，或者不涂。可以发现涂 $1, 2$ 号和涂 $0$ 号本质相同且没有其他方案。
对于第三个蒜头，可以涂两个，可以涂一个，可以不涂，总共三种方案。
### 数据范围：
$1\leq T\leq 20,\ 2\leq n< 998244353$ 。
对于前 $5$ 个测试点：有些数据是随机的。
对于第 $6$ 个测试点： $n\leq 20$ 。
对于第 $7$ 个测试点： $T = 1$ 。
对于第 $8$ 个测试点： 数据随机。
对于第 $9$ 个测试点： $n\leq 10^6$ 。
对于第 $10$ 个测试点： 保证数据是手工构造的。
### 温馨提示：
本题不卡常。 std 使用 cin, cout 输入输出数据，最慢点 200ms 左右。