P11009 'STA - R7' Summation

Lloyd has a positive integer $t$, with the initial value $t=2$ or $t=3$. Each time, he can increase $t$ by $2^t$ or by $\lfloor\log_2(t-1)\rfloor$. Let $f(x)$ be the minimum number of operations needed to obtain $t=x$. If $x$ cannot be obtained by operations, then $f(x)=0$. Now you are given a positive integer $n$. You need to compute $\sum_{i=1}^n f(i)$. The answer may be very large, so output it modulo $998244353$.

**This problem has multiple test cases.** The first line contains a positive integer $T$, representing the number of test cases. The next $T$ lines each contain a positive integer $n$, describing one query.

Output $T$ lines, one for each query. Print the answer modulo $998244353$.

Constraints: - Subtask 1 (10 pts): $n\le 10^7$. - Subtask 2 (30 pts): $T=1$. - Subtask 3 (30 pts): $n\le2^{40}$. - Subtask 4 (30 pts): No special constraints. For all testdata, $1\le T\le 10^4$, $1\le n\le2^{60}$. Translated by ChatGPT 5