## Reverse Xor

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Let $$reverse(x)$$ be the function that reverses the binary representation of x and returns the resulting number,for example $$reverse(3)=3$$, $$reverse(2)=1$$,$$reverse(6)=3$$

We define $$f(x)= \begin{cases} 0 & \text{if} x = 0 \\ f(x \oplus reverse(x))+1 & \text{otherwise} \end{cases}$$

Given an integer $$n$$, you are asked to calculate $$\sum^{2^{n}-1}_{i=1} f(i)$$ modulo $$998244353$$

#### Input Specification

The first line contains one integer $$t$$ $$(1\leq t \leq 10^4)$$ the number of test cases.

Each test case consists of one integer $$n$$ $$(1\leq n \leq 10^9)$$

#### Output Specification

For each test case, output one integer on a separate line : the answer to the problem.

#### Sample Input

4
1
3
5
69420

#### Sample Output

1
10
58
731673111

#### Scoring

\begin{array}{|c|c|c|} \hline \text{Group} & \text{Points} & \text{Constraints} \cr \hline 1 & 20 & 1 \leq n \leq 20 \cr \hline 2 & 45 & 1 \leq n \leq 3.10^5 \cr \hline 3 & 35 & \text{ No additional constraints } \cr \hline \end{array}