Description

b6e0 has a towering tree. This rooted binary tree has infinitely many nodes. The root is numbered $1$. For every $x(x\ge1)$, the node numbered $x$ has children numbered $2x$ and $2x+1$.

Among the nodes with numbers $\le n$, you need to choose two nodes (they may be the same), and find the sum of the numbers of their lowest common ancestors over all choices. That is, compute (where $\operatorname{LCA}(i,j)$ denotes the number of the lowest common ancestor of $i$ and $j$):

It is guaranteed that there exists a natural number $k$ such that $n=2^k-1$.

Take the answer modulo $998244353$.

Input Format

This problem has multiple queries.

The first line contains a positive integer $t$, the number of queries.

The next $t$ lines each contain a natural number $k$, meaning that in the $i$-th query $n=2^k-1$.

Output Format

Output $t$ lines. The $i$-th line should be the answer for the $i$-th query modulo $998244353$.

2
2
3

12
88

Hint

[Sample Explanation]

For the first query, $n=2^2-1=3$, and the answer is $1+1+1+1+2+1+1+1+3=12$.

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (20 pts): $k\le8$.
• Subtask 2 (20 pts): $t,k\le300$.
• Subtask 3 (20 pts): $k\le10^4$.
• Subtask 4 (40 pts): no special constraints.

For $100\%$ of the testdata, $1\le t,k\le10^6$.

Translated by ChatGPT 5