在这个充满缺陷的悲伤世界中,存在丑陋的线段树。
线段树是一棵树,其中每个节点代表一个线段并具有其编号。可以以递归方式构建 $$$n$$$ 元素数组的线段树。假设函数 $$$\operatorname{build}(v,l,r)$$$ 构建以编号为 $$$v$$$ 的节点为根的线段树,它对应于线段 $$$[l,r]$$$。
现在让我们定义 $$$\operatorname{build}(v,l,r)$$$:
- 如果 $$$l=r$$$,则此节点 $$$v$$$ 是叶子,因此我们停止添加更多边
- 否则,我们添加边 $$$(v, 2v)$$$ 和 $$$(v, 2v+1)$$$。令 $$$m=\lfloor \frac{l+r}{2} \rfloor$$$。然后我们调用 $$$\operatorname{build}(2v,l,m)$$$ 和 $$$\operatorname{build}(2v+1,m+1,r)$$$。
因此,整个树是通过调用 $$$\operatorname{build}(1,1,n)$$$ 构建的。
现在 Ibti 将为包含 $$$n$$$ 元素的数组构造一棵线段树。他想要求 $$$\operatorname{lca}^\dagger(S)$$$ 的总和,其中 $$$S$$$ 是叶子的非空子集。请注意,恰好有 $$$2^n - 1$$$ 可能的子集。由于这个和可能非常大,因此输出它对 $$$998\,244\,353$$$ 取模。
$$$^\dagger\operatorname{lca}(S)$$$ 是 $$$S$$$ 中节点的最小公共祖先的编号。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^{18}$$$) - 为其构建线段树的数组的长度。
输出
对于每个测试用例,输出一个整数 - 所需的总和模 $$$998\,244\,353$$$。
示例
输入 #1
5 2 3 4 5 53278
输出 #1
6 17 36 69 593324855
注意
在第一个测试用例中:
让我们看看叶子的所有子集。
- $$$\operatorname{lca}(\{2\})=2$$$;
- $$$\operatorname{lca}(\{3\})=3$$$;
- $$$\operatorname{lca}(\{2,3\})=1$$$。
因此,答案是$$$2+3+1=6$$$。
在第二个测试用例中:
让我们看看叶子的所有子集。
- $$$\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$$$。