P6826 "EZEC-4" Moonlit Light-Flower Dance

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

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

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 $T$ lines. Each line contains one integer, representing the result of each query modulo $998244353$.

**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](https://baike.baidu.com/item/对数公式/5557846?fr=aladdin). Translated by ChatGPT 5