E. One-X

每个测试点时间限制：$3$ 秒

每个测试点内存限制：$512$ 兆字节

在这个充满缺陷的悲伤世界里，丑陋的线段树真实存在。

一棵线段树是一棵树，其中每个节点都表示一个区间，并且每个节点都有一个编号。对于一个长度为 $n$ 的数组，可以递归地构建对应的线段树。设函数 build(v, l, r) 表示构建以编号为 $v$ 的节点为根的线段树，并且该节点对应区间 $[l, r]$。

现在定义 build(v, l, r) 的过程如下：

• 如果 $l = r$，那么节点 $v$ 是叶子节点，不再继续连边。
• 否则，加入边 $(v, 2v)$ 和 $(v, 2v+1)$。令

$$m = \left\lfloor \frac{l+r}{2} \right\rfloor$$

随后递归调用：

$$\text{build}(2v, l, m), \quad \text{build}(2v+1, m+1, r) $$

整棵树通过调用：

$$\text{build}(1, 1, n)$$

来构建完成。

现在，Ibti 将为一个长度为 $n$ 的数组构造这样一棵线段树。他想要求出所有非空叶子节点子集 $S$ 的 $\operatorname{lca}(S)$ 之和。注意，叶子节点的非空子集一共有恰好 $2^n - 1$ 个。由于这个和可能非常大，你需要输出它对 $998244353$ 取模后的结果。

这里，$\operatorname{lca}(S)$ 表示集合 $S$ 中所有节点的最近公共祖先节点的编号。

输入格式

每个输入包含多组测试数据。

第一行包含一个整数 $t$，表示测试数据组数，其中：

$$1 \le t \le 10^3$$

对于每组测试数据：

第一行包含一个整数 $n$，表示构建线段树的数组长度，其中：

$$2 \le n \le 10^{18}$$

输出格式

对于每组测试数据，输出一个整数，表示所求答案对 $998244353$ 取模后的结果。

样例输入

5
2
3
4
5
53278

样例输出

6
17
36
69
593324855

说明

在第 $1$ 组测试数据中：

我们考察所有叶子节点的非空子集：

$$\operatorname{lca}(\{2\}) = 2$$ $$\operatorname{lca}(\{3\}) = 3$$ $$\operatorname{lca}(\{2,3\}) = 1$$

因此答案为：

$$2 + 3 + 1 = 6$$

在第 $2$ 组测试数据中：

我们考察所有叶子节点的非空子集：

$$\operatorname{lca}(\{4\}) = 4$$ $$\operatorname{lca}(\{5\}) = 5$$ $$\operatorname{lca}(\{3\}) = 3$$ $$\operatorname{lca}(\{4,5\}) = 2$$ $$\operatorname{lca}(\{4,3\}) = 1$$ $$\operatorname{lca}(\{5,3\}) = 1$$ $$\operatorname{lca}(\{4,5,3\}) = 1$$

因此答案为：

$$4 + 5 + 3 + 2 + 1 + 1 + 1 = 17$$