题目描述

有 $n$ 个人，编号为 $1$ 到 $n$，坐在环上玩约瑟夫。

他们从 $1$ 到 $m$ 循环报数，与正常约瑟夫不同的是，没有报到 $1$ 的人都会被淘汰，直至只有一个人活下来为止。

设活下来的人编号为 $x$，则记 $J_m(n)=x$。

给定 $m,l,r$，求 $\sum_{i=l}^{r}J_m(i)$，输出对 $998244353$ 取模。

输入格式

本题有多组数据。

第一行一个正整数 $T$，表示数据组数。

对于每组数据：

一行三个整数，依次为 $m,l,r$。

输出格式

对于每组数据：

输出一行一个整数，表示答案对 $998244353$ 取模的结果。

4
2 1 4
3 3 7
8 12 64
2 1 1048976

6
17
1149
148359175

提示

本题采用捆绑测试。

• Subtask 1（4 pts）：$T=1$，$m \leq 10$，$r \leq 200$。
• Subtask 2（8 pts）：$T=1$，$m \leq 10^6$，$r\leq 10^7$。
• Subtask 3（8 pts）：$\sum (r-l+1) \leq 2 \times 10^6$。
• Subtask 4（10 pts）：$m=2$。
• Subtask 5（25 pts）：$T \leq 5$，$m \leq 10^6$。
• Subtask 6（45 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \leq T \leq 10^4$，$2 \leq m \leq 10^{12}$，$1 \leq l \leq r \leq 10^{18}$。