题目描述

b6e0 有一棵参天大树。这棵二叉有根树有无数多个节点。它的根节点的编号为 $1$，对于每一个 $x(x\ge1)$，编号为 $x$ 的节点有编号为 $2x$ 和 $2x+1$ 的子节点。

你需要在编号小于等于 $n$ 的节点中，选出两个可以相同的节点，求出所有情况中它们的最近公共祖先的编号的和。也就是求（其中 $\operatorname{LCA}(i,j)$ 表示 $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$。