6807: 开关灯

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

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

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

 n =3 时每种状态的一种可能操作方式如下（其中ri表示在编号为i的灯上操作）： 
(0, 0, 0) 
(0, 0, 0) r1 −→ (1,1,0) r2 −→ (0,0,1) r3 −→ (0,1,0)
(0, 0, 0) r3 −→ (0,1,1) 
(0, 0, 0) r2 −→ (1,1,1) r3 −→ (1,0,0)
(0, 0, 0) r1 −→ (1,1,0) r3 −→ (1,0,1)
(0, 0, 0) r1 −→ (1,1,0)
(0, 0, 0) r2 −→ (1,1,1)