Background

The light flowers under the moon, dancing with the gentle breeze, bring back memories of you and me......

Problem Description

In the Light-Flower Forest, there are light-flower trees numbered from $l$ to $r$. For the tree numbered $i$, there are $i - 1$ such trees. The Light-Flower Forest is very beautiful, so each tree has $n$ light flowers numbered $1\sim n$. If the light flower numbered $j$ on the tree numbered $i$ falls, it produces a charm value of $\left\lceil\log_i j\right\rceil$.

When night falls, all light flowers on all trees fall. The "flower fan" (just kidding) tlx wants to know the total charm value, but calculating it only once is too easy, so he will set up different scenarios and ask you $T$ times. Since the answer is very large, you only need to output the total charm value modulo $998244353$.

One-sentence statement: There are $T$ queries. Each time you are given three integers $l, r, n$, and you need to compute the value of the following expression:

$$\sum_{i=l}^r(i-1)\sum_{j=1}^n \left\lceil\log_ij\right\rceil\;\;\bmod998244353$$

Input Format

The first line contains an integer $T$, representing the number of queries.

The next $T$ lines each contain three integers $l, r, n$, representing the starting tree index, the ending tree index, and the number of light flowers on each tree.

Output Format

Output $T$ lines. Each line contains one integer, representing the result of each query modulo $998244353$.

1
2 3 5

20

2
23333 23333 233233
114514 19260817 1919810   

356712294
125194507

Hint

Constraints

This problem uses bundled testdata. The specific constraints are as follows:

• Subtask 1 $(1\text{ pts})$: $T = 1$, $n = 1$.
• Subtask 2 $(9\text{ pts})$: $l = r = 2$.
• Subtask 3 $(10\text{ pts})$: $T = 1$, $n\leq 10^3$, $r\leq 10^3$.
• Subtask 4 $(10\text{ pts})$: $l = r\not=2$.
• Subtask 5 $(20\text{ pts})$: $T = 1$, $n\leq 10^6$.
• Subtask 6 $(20\text{ pts})$: $T = 1$, $r\leq 10^6$.
• Subtask 7 $(20\text{ pts})$: $T\leq 3000$.
• Subtask 8 $(10\text{ pts})$: No special restrictions, time limit $1.5\;\text{s}$.

For all testdata, it holds that:

$1\leq T\leq 10^5$, $1\leq n\leq 10^{18}$, $2\leq l\leq r\leq 10^{18}$.

Note: Any constraints not mentioned in the subtasks use the maximum constraints.

---

Sample Explanation #1

$$\left\lceil\log_21\right\rceil+\left\lceil\log_22\right\rceil+\left\lceil\log_23\right\rceil+\left\lceil\log_24\right\rceil+\left\lceil\log_25\right\rceil=8$$$$\left\lceil\log_31\right\rceil+\left\lceil\log_32\right\rceil+\left\lceil\log_33\right\rceil+\left\lceil\log_34\right\rceil+\left\lceil\log_35\right\rceil=6$$

Therefore:

$$ans=8×(2-1)+6×(3-1)=20$$

For Sample #2, I believe your smart brain can get the answer in no time.

---

Other Hints

If you do not understand logarithm ($\log$) operations, you can check here.

Translated by ChatGPT 5