Background

Before dawn arrives, someone must light up the darkness.

Problem Description

Xs_siqi gives you $2^n$ vertices. There is a directed edge from $x$ to $y$ if and only if $x \operatorname{xor} y = 2^k$, $k \in [0,n)$, and $x > y$. Here, $\operatorname{xor}$ means bitwise XOR, and $k$ is an integer. Let $f_{x,y}$ be the number of different paths from vertex $x$ to vertex $y$. Find:

Output the answer modulo $998244353$.

Input Format

The first line contains an integer $t$.

The next $t$ lines (lines $2$ to $t+1$) each contain an integer $n$.

Output Format

Output $t$ lines. Each line contains an integer representing the number of valid paths required by the problem.

4
2
3
50
999998

2
15
599192517
81627972

Hint

Sample Explanation #1

For the first test case of the sample, vertex $3$ has edges to $1$ and $2$. Then there is one path from $3$ to $1$ and one path from $3$ to $2$, for a total of $2$ paths.

Constraints

For all testdata: $1 \le t \le 10^6$, $1 \le n \le 10^7$.

Translated by ChatGPT 5