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

Here, \oplus denotes the [bitwise XOR operation] and 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(6)=3, reverse(7)=7

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

------ Input Format ------ 

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

------ Output Format ------ 

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

------ Constraints ------ 

$1 ≤ T ≤ 3 \cdot 10^{5}$
$1 ≤ N ≤ 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 1 ------ 
Note that: 

- $f(1) = f(1 \oplus 1) + 1 = f(0) + 1 = 1$
- $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 \oplus 3) + 1 = f(0) + 1 = 1$

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

Difficulty: VERY_HARD
Tags: Bit manipulation

Mathematics
Skill types: Bit manipulation

Starter code:

Solutions:
from sys import stdin, setrecursionlimit
input = stdin.readline
mod = 998244353

def add(a, b):
	return (a % mod + b % mod) % mod

def mul(a, b):
	return a % mod * (b % mod) % mod

def sub(a, b):
	return (a - b + mod) % mod

def answer():
	if n == 1:
		return 1
	even = pow(2, n - 1, mod)
	ans = mul(2, even)
	ans = sub(ans, 2)
	if n & 1:
		pal = mul(2, sub(pow(2, n // 2, mod), 1))
		pal = add(pal, pow(2, n // 2, mod))
	else:
		pal = mul(2, sub(pow(2, n // 2, mod), 1))
	ans = add(ans, pal)
	odd = sub(pow(2, n, mod), even)
	leftodd = sub(odd, pal)
	ans = add(ans, mul(3, leftodd))
	return ans
for T in range(int(input())):
	n = int(input())
	print(answer())


tl = int(input())
mod = 998244353
while tl:
	tl = tl - 1
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(4)
	else:
		if n % 2 == 0:
			x = pow(2, n // 2, mod) % mod
			pal = 2 * (x - 1) % mod
			nonpal = pow(2, n - 1, mod) % mod
			ans = (5 * nonpal % mod - 2 - 2 * pal) % mod
		else:
			pal = (3 * pow(2, (n - 1) // 2, mod) - 2) % mod
			nonpal = pow(2, n - 1, mod) % mod
			ans = (5 * nonpal % mod - 2 - 2 * pal) % mod
		print(ans)


from math import ceil
mod = 998244353
for _ in range(int(input())):
	n = int(input())
	temp = pow(2, n - 1, mod)
	ans = 2 * (temp - 1) % mod
	if n % 2:
		cnt = (2 * (pow(2, n // 2, mod) - 1) + pow(2, n // 2, mod)) % mod
	else:
		cnt = 2 * (pow(2, n // 2, mod) - 1) % mod
	ans = (ans + 3 * (temp - cnt) + cnt) % mod
	print(ans)


t = int(input())
mod = 998244353
while t:
	t = t - 1
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(4)
	else:
		if n % 2 == 0:
			tot = (pow(2, n, mod) - 1) % mod
			pal = 2 * (pow(2, n // 2, mod) - 1) % mod
			nonpal = pow(2, n - 1, mod) % mod
			ans = (2 * tot + nonpal - 2 * pal) % mod
		else:
			tot = (pow(2, n, mod) - 1) % mod
			pal = (3 * pow(2, (n - 1) // 2, mod) - 2) % mod
			nonpal = pow(2, n - 1, mod) % mod
			ans = (2 * tot + nonpal - 2 * pal) % mod
		print(ans)


def main():
	n = int(input())
	mod = 998244353
	if n == 1:
		return 1
	if n == 2:
		return 4
	if n == 3:
		return 10
	a = 10 * pow(2, n - 2, mod) + 2
	b = 2 * pow(2, (n + 1) // 2, mod)
	c = 2 * pow(2, n // 2, mod)
	return (a - b - c) % mod
for _ in range(int(input())):
	print(main())