Reverse Xor


Submit solution

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}


Comments

There are no comments at the moment.