开关灯

Problem Description

Yoshinow有一排灯，按 $1$ 到 $n$ 的顺序从左到右编号，开始时所有灯全是关闭的。每次操作可以选择一盏灯，同时反转这盏灯及其左右两盏灯（如果存在）的开/关状态（即关变开、开变关） 现在可以对这些灯做任意多次（可以是零次）操作，Yoshinow想问你，这排灯共有多少种不同状态是可以到达的，由于答案可能很大，需要输出其对 $998\ 244\ 353$ 取模的结果。 称两种状态不同，当且仅当两个状态中，存在至少一盏灯的开/关状态不同。

Input

第一行输入一个正整数 $T$ ,表示一共有 $T$ 组测试用例，$1 \leq T \leq 100$. 接下来 $T$ 行，每行输入一个整数 $n$，即题目描述的电灯数量。$1\leq n\leq 10^9$.

Output

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

Sample Input

2
3
4

Sample Output

8
16

Hint

$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)$

Source

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