「PMOI-2」参天大树

b6e0 有一棵参天大树。这棵二叉有根树有无数多个节点。它的根节点的编号为 $1$，对于每一个 $x(x\ge1)$，编号为 $x$ 的节点有编号为 $2x$ 和 $2x+1$ 的子节点。 你需要在编号小于等于 $n$ 的节点中，选出两个**可以相同**的节点，求出所有情况中它们的最近公共祖先的编号的和。也就是求（其中 $\operatorname{LCA}(i,j)$ 表示 $i$ 与 $j$ 的最近公共祖先的编号）： $$\sum_{i=1}^n\sum_{j=1}^n \operatorname{LCA}(i,j)$$ 保证存在一个自然数 $k$，满足 $n=2^k-1$。 **答案对 $998244353$ 取模。**

**本题有多组询问。** 第一行一个正整数 $t$ 表示询问的次数。 下面 $t$ 行，每行一个自然数 $k$，表示第 $i$ 次询问的 $n=2^k-1$。

输出 $t$ 行，第 $i$ 行表示第 $i$ 次询问的答案**对 $998244353$ 取模**的值。

2
2
3

12
88

【样例解释】 对于第一次询问，$n=2^2-1=3$，答案为 $1+1+1+1+2+1+1+1+3=12$。 【数据范围】 **本题采用捆绑测试。** - Subtask1（20pts）：$k\le8$； - Subtask2（20pts）：$t,k\le300$； - Subtask3（20pts）：$k\le10^4$； - Subtask4（40pts）：无特殊限制。 对于 $100\%$ 的数据，$1\le t,k\le10^6$。