题目描述

有 $n$ 个布尔变量组成数列 $a_1, a_2, a_3, \cdots, a_n$。对于初值为任意非负整数的变量 $x, y$，按照整数 $i$ 从 $n-1$ 到 $1$ 的顺序，分情况执行以下操作（$\oplus$ 表示二进制按位异或）：

统计不同数列 $a_1, a_2, a_3, \cdots, a_n$ 的数量，满足在该数列上，对初值为任意非负整数的变量 $x, y$ 执行上述所有操作，结果总是使这两个变量交换它们的初始值（也就是说，$x$ 的终值是 $y$ 的初值，$y$ 的终值是 $x$ 的初值）。答案对 $998244353$ 取模。

输入格式

本题包含多组测试数据。

第一行输入一个正整数 $T$ （$1 \leq T \leq 10$）表示测试数据组数。

对于每一组测试数据： 输入的唯一一行包含一个正整数 $n$ （$1 \leq n \leq 10^{18}$）表示数列的预期长度。

输出格式

对于每一组测试数据，输出包含一行一个非负整数表示满足条件的数列数量对 $998244353$ 取模后的值。

3
1
2
4

0
0
2