T158719 「THP3考前信心赛」B 空海澄澈

高动态范围的影像也好， 极富日本风味的情景也好， 都敌不过真正的天空的颜色。 仍持有这种上个时代的认识的人，恐怕已经不存在了吧。 虚拟的感觉，比起现实更能刺激人类的感官。 就好像梦与现实无法区分一样，就好像人类与蝴蝶无法区分一样， 虚拟与现实是绝对无法区分的，这是现在人们的常识。 身与华落，心将香飞。 毫无疑问，虚拟正是人类的本质。 《卯酉东海道》·最澄澈的空与海·附带故事

这里曾经有一个寓意深长的题面，但是 Luckyblock 觉得会引发深思影响做题就删掉了。 定义： $$f(n) = \sum_{i=1}^{n}\gcd(i,n)$$ $m$ 次询问，每次询问给定参数 $l,r$，求： $$\sum_{i=l}^{r}f(i)\pmod {998244353}$$

第 $1$ 行 $1$ 个正整数，代表 $m$。 第 $2\sim m+1$ 行，每行两个正整数，代表一次询问的 $l,r$。

输出 $m$ 行，每行 $1$ 个正整数，代表第 $i$ 次询问的答案。

本题共有 10 个测试点。 对于测试点 $1$，保证 $l=r=1$。 对于测试点 $2$，保证 $1\le l\le r\le 3$。 对于测试点 $3\sim 4$，保证 $m\le 2000, 1\le l\le r\le 2000$。 对于所有测试点，保证 $1\le m\le 10^6$，$1\le l \le r\le 10^6$。 --- 本题读入数据量较大，请使用较快的读入方式。 样例三太大了传不上来= = 如果需要请飞鸽私信 wjs-025 获取