Description

Xs_siqi 给了你 $2^n$ 个点，$x$ 到 $y$ 有有向边当且仅当 $x\operatorname{xor} y=2^k,k \in [0,n)$，且 $x>y$。其中，$\operatorname{xor}$ 表示按位异或，$k$ 为整数。令 $f_{x,y}$ 为 $x$ 点到 $y$ 点的不同路径数，求：

答案对 $998244353$ 取模。

Input Format

第一行，一个整数 $t$。

接下来 $2 \sim t+1$ 行，一行一个整数表示 $n$。

Output Format

共 $t$ 行，每行一个整数表示题目要求的方案数。

4
2
3
50
999998

2
15
599192517
81627972

Hint

【样例解释 #1】

对于样例的第一组，$3$ 向 $1,2$ 连边，这样 $3$ 到 $1$ 是一个方案，$3$ 到 $2$ 是一个方案，一共有 $2$ 个方案。

【数据范围】

对于全部数据保证：$1 \le t \le 10^6$，$1 \le n \le 10^7$。