P7419 "PMOI-2" Towering Tree

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$): $$\sum_{i=1}^n\sum_{j=1}^n \operatorname{LCA}(i,j)$$ It is guaranteed that there exists a natural number $k$ such that $n=2^k-1$. **Take the answer modulo $998244353$.**

**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 $t$ lines. The $i$-th line should be the answer for the $i$-th query **modulo $998244353$**.

[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