题目限制

1000 ms 1024 M

题目描述

题目背景

数论中，有一个很重要的函数：$\varphi$。其定义为：$\varphi(x) = \sum\limits_{i = 1}^{x} [\gcd (i, x) = 1]$，也就是 $\leq x$的正整数当中与 x 互质的数的个数。显然，除 $1$ 以外，每个正整数 $x$ 都满足$\varphi(x) < x$。 数论中，又有一种迭代函数：我们称 $f^{(k)} (x) = f(\dots f(x))$，恰好有 $k$ 个 $f$。特别地，$k\leq 0$ 时，定义 $f^{(k)} (x) = x$。 日记想要把它们结合起来。

题目描述

日记认为，$\varphi$ 函数不够美观。因此，日记定义了 $f(x) = \varphi^{(m(x)-B)} (x)$，其中 $B$ 为一个常数，$m(x)=\max_{i=1}^{m}\varphi(i)$。

日记知道，有一种科技可以快速求出 $\varphi$ 函数的区间和（即，$\sum\limits_{i=L}^{R} \varphi(i)$）。所以，她认定，也有一种科技可以快速求出 $f$ 函数的区间和（即，$\sum\limits_{i=L}^{R} f(i)$）。但她太菜了，并不会这种科技。所以，她想请你帮个忙。

简要题意：先给定常数 $B, T$，并给定 $T$ 组 $L, R$，求 $\sum\limits_{i=L}^{R} \varphi^{(\max_{j=1}^{i}\varphi(j)-B)} (i)$。

日记不会这种科技，数据怎么造的？

日记：暴力啊，但是你的程序只有 1s 的时间喵 /mgx

输入格式

第 $1$ 行，$2$ 个非负整数 $T, B$，代表数据组数和常数。

接下来 $T$ 行，每行 $2$ 个正整数 $L, R$，代表你要求出 $\sum\limits_{i=L}^{R} f(i)$ 的值。

输出格式

$T$ 行，每行 $1$ 个正整数，代表答案。请注意，你可能需要 C++ 内置整型以外的类型来存储答案。

数据范围

本题设置 25 个测试点，每个测试点 4 分。同时，每个测试点满足一些限制，见下：

对全部数据，保证 $1 \leq T \leq 10^5$，$1 \leq L \leq R \leq 10^9$，$0 \leq B \leq 10^9$。

输入样例 1

5 4
1 3
2 4
3 5
4 6
5 7

输出样例 1

6
9
12
15
13