You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

线段树覆盖区间计数

题目描述

线段树是一种非常常见的数据结构，一棵下标属于整数区间 $[1, n]$ 的线段树可以这么构造：

• 初始线段树只有一个结点 $[1, n]$。
• 对于结点 $[L, R]$，若 $L < R$，则令 $mid = \left[ \frac{L + R}{2} \right]$（$[x]$ 表示不超过 $x$ 的最大整数），则这个结点有两个子结点 $[L, mid]$、$[mid + 1, R]$。

对一个区间$[a,b]$，定义$f([a,b])$为要不重不漏地覆盖区间$[a,b]$，需要使用的线段树结点的最小数量。现在对$[1,n]$内的所有区间$[a,b]$，求$f([a,b])$之和，即$\sum_{1\le a \le b\le n} f([a,b])$。有$T$组询问，由于结果可能很大，请输出答案模$998244353$的结果。

输入格式

第一行一个正整数 $T$ 表示数据组数。 接下来 $T$ 行，其中第 $i$ 行一个正整数 $n$ 表示第 $i$ 组数据。

输出格式

$T$ 行，第 $i$ 行一个整数表示第 $i$ 组数据的答案模$998244353$的结果。

样例 #1

样例输入 #1

1
3

样例输出 #1

7

提示

样例解释 #1

$f([1, 1]) = f([2,2]) = f([3,3]) = f([1,2]) = f([1,3]) = 1$，$f([2, 3]) = 2$，故总和为 $7$ 。

数据范围

对$20\%$的数据，$1\le T\le 10$，$1\le n\le 1000$；

对$60\%$的数据，$1\le T\le 100$，$1\le n\le 10^5$；

对$100\%$的数据，$1 \le T \le 1000$，$1 \le n \le {10}^{18}$。