『STA - R7』求和

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}$。