Xor Becoming Uncanny

 We define 

f(x)={f(x⊕reverse(x))+10if x≠0otherwise$f(x)=\{\begin{array}{ll}f(x\oplus reverse(x))+1& \text{if }x\ne 0\\ 0& \text{otherwise}\end{array}$

Here, ⊕$\oplus$ denotes the bitwise XOR operation and reverse$reverse$ is a function that takes a postive integer, reverses its binary representation (without any leading zeros) and returns the resulting number. For example reverse(2)=1$reverse(2)=1$, reverse(6)=3$reverse(6)=3$, reverse(7)=7$reverse(7)=7$

Given an integer N$N$, find out the value of ∑2N−1i=1f(i)$\sum _{i=1}^{2^N-1}f(i)$ modulo 998244353$998244353$ or claim that there exists a positive integer x$x$ <2N$<2^N$ for which f$f$ is undefined.

Input Format

• The first line of input contains a single integer T$T$ - the number of test cases. The description of T$T$ test cases follows.
• The first and only line of each test case contains a single integer N$N$.

Output Format

• For each test case output a single line containing one integer :
  • −1$-1$ if there exists a positive integer x$x$ such that x<2N$x<2^N$ and f(x)$f(x)$ is undefined
  • ∑2N−1i=1f(i)$\sum _{i=1}^{2^N-1}f(i)$ modulo 998244353$998244353$ otherwise

Constraints

• 1≤T≤3⋅105$1\le T\le 3\cdot {10}^5$
• 1≤N≤109$1\le N\le {10}^9$

Sample Input 1 

8
1
2
3
5
8
13
21
34

Sample Output 1 

1
4
10
58
578
20098
5236738
24641495

Explanation

Note that:

• f(1)=f(1⊕1)+1=f(0)+1=1$f(1)=f(1\oplus 1)+1=f(0)+1=1$

• f(2)=f(2⊕1)+1=f(3)+1=(f(3⊕3)+1)+1=(f(0)+1)+1=2$f(2)=f(2\oplus 1)+1=f(3)+1=(f(3\oplus 3)+1)+1=(f(0)+1)+1=2$

• f(3)=f(3⊕3)+1=f(0)+1=1$f(3)=f(3\oplus 3)+1=f(0)+1=1$

• Test case-1: ∑21−1i=1f(i)=f(1)=1$\sum _{i=1}^{2^1-1}f(i)=f(1)=1$. So answer is 1 mod 998244353=1$1\text{ mod }998244353=1$.

• Test case-2: ∑22−1i=1f(i)=f(1)+f(2)+f(3)=1+2+1=4$\sum _{i=1}^{2^2-1}f(i)=f(1)+f(2)+f(3)=1+2+1=4$. So answer is 4 mod 998244353=4$4\text{ mod }998244353=4$.

• Tweet
• Share
• Share
• Share
• Share

Related Post