题目描述

Lloyd 有一个正整数 $t$，初始 $t=2$ 或 $t=3$。每次他可以令 $t$ 加上 $2^t$ 或者 $\lfloor\log_2(t-1)\rfloor$。

令 $f(x)$ 是操作得到 $t=x$ 的最小操作次数，若无法操作得到 $x$ 则 $f(x)=0$。

现在给定一个正整数 $n$，你需要求 $\sum_{i=1}^nf(i)$ 的值。答案可能很大，对 $998244353$ 取模。

输入格式

本题有多组测试。

第一行一个正整数 $T$ 表示数据组数。

后 $T$ 行一行一个正整数 $n$ 描述一组询问。

输出格式

$T$ 行，每行回答一个询问。答案对 $998244353$ 取模。

7
1
10
1000000
10000000
1000000000
1000000000000
1000000000000000000

0
16
922782102
752337093
360487662
955916859
689020696

提示

数据范围：

• Subtask 1 (10pts)：$n\le 10^7$。
• Subtask 2 (30pts)：$T=1$。
• Subtask 3 (30pts)：$n\le2^{40}$。
• Subtask 4 (30pts)：无特殊限制。

对于全部数据，$1\le T\le 10^4$，$1\le n\le2^{60}$。