开关灯

Yoshinow有一排灯，按 $1$ 到 $n$ 的顺序从左到右编号，开始时所有灯全是关闭的。每次**操作**可以选择一盏灯，同时反转这盏灯**及其**左右两盏灯（如果存在）的开/关状态（即关变开、开变关）

现在可以对这些灯做任意多次（可以是零次）操作，Yoshinow想问你，这排灯共有多少种不同状态是可以到达的，由于答案可能很大，需要输出其对 $998\ 244\ 353$ 取模的结果。

称两种状态不同，当且仅当两个状态中，存在至少一盏灯的开/关状态不同。

第一行输入一个正整数 $T$ ,表示一共有 $T$ 组测试用例，$1 \leq T \leq 100$.

接下来 $T$ 行，每行输入一个整数 $n$，即题目描述的电灯数量。$1\leq n\leq 10^9$.

对每个测试用例，输出一行一个整数表示答案。

2
3
4

8
16

$n=3$ 时每种状态的一种可能操作方式如下（其中 $r_i$ 表示在编号为 $i$ 的灯上操作）：

- $(0,0,0)$

- $(0,0,0)\xrightarrow{r_1}(1,1,0)\xrightarrow{r_2}(0,0,1)$

- $(0,0,0)\xrightarrow{r_1}(1,1,0)\xrightarrow{r_2}(0,0,1)\xrightarrow{r_3}(0,1,0)$

- $(0,0,0)\xrightarrow{r_3} (0,1,1)$

- $(0,0,0)\xrightarrow{r_2}(1,1,1)\xrightarrow{r_3}(1,0,0)$

- $(0,0,0)\xrightarrow{r_1}(1,1,0)\xrightarrow{r_3}(1,0,1)$

- $(0,0,0)\xrightarrow{r_1} (1,1,0)$

- $(0,0,0)\xrightarrow{r_2}(1,1,1)$

2024“钉耙编程”中国大学生算法设计超级联赛（5）