P17517 [ECUSTPC 2026 Fall] 根除

> *我们终于等来了黎明，可这座城的*根除*了记得黑夜，似乎什么也没能留下。*

我们通常会把一个较大的数字的开根分解为最简的根式，例如 $\sqrt{432} = 12 \sqrt3$。 在 $\mathbb{N}$ 上定义数论函数 $f(n) = \min\{a \mid n = ab^2, a, b \in \mathbb{N}\}$，即函数值为满足等式的最小自然数 $a$，可以发现这样的 $a$ 总是存在的。 给定 $q$ 次询问，每次询问给定 $l, r$，请分别求出 $\sum_{i=l}^r f(i)$ 的答案在模 $998\,244\,353$ 下的值。

第一行输入一个整数 $q$ ($1 \le q \le 500$)，表示询问的数量。 随后输入 $q$ 行两个整数 $l$ 和 $r$ ($1 \le l \le r \le 10^{12}$)，表示一次询问的区间。

对于每次询问，输出一行一个整数，表示 $\sum_{i=l}^r f(i)$ 在模 $998\,244\,353$ 下的值。

### 样例 1 解释 对于第 2 次和第 3 次询问，对应的 $f$ 值为： $$ \begin{array}{c|ccccccccccccccc} n &1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\ \hline f(n) &1&2&3&1&5&6&7&2&1&10&11&3&13&14&15 \end{array} $$ 其中第 3 次询问即为 $$ \sum_{i = 10}^{15}f(i) = f(10) + f(11) + f(12) + f(13) + f(14) + f(15) = 10 + 11 + 3 + 13 + 14 + 15 = 66. $$