Problem Description

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$.

Input Format

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 Format

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

7
1
10
1000000
10000000
1000000000
1000000000000
1000000000000000000

0
16
922782102
752337093
360487662
955916859
689020696

Hint

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