对于 $\forall i \in [1,n]$，$f(x)=\varphi^{m(x)-B}(x)$。易发现 $m(x)-B$ 不下降，且 $\varphi(x) \leq x$。

由于 $x \ne 1$ 且 $x$ 为奇数时 $\varphi(x)$ 为偶数，$x$ 为偶数时 $x \geq 2\varphi(x)$，所以有另一个结论是使 $\varphi^{k}(x)=1$ 的正整数 $k$ 的最小值不大于 $2 \log n$。

因此考虑找出最小的 $x=x_0$ 使 $m(x_0)>B$。这样对于 $x<x_0$，$f(x)=x \Longrightarrow \sum_{i=1}^{x}f(i)=\frac{x(x+1)}{2}$。再考虑找出最大的 $x=x_1$ 使 $m(x_1)-B \leq 2 \log n$，这样对于 $x>x_1$，有 $f(x)=1$。

设 $x_1-x_0=k$，显然 $k$ 的数值不会太大。因此考虑预处理出 $x_0$ 和 $x_1$ 和 $f(x_0 \sim x_1)$，那么就可以在 $O(1)$ 的时间内求出任意 $\sum_{i=1}^{n}f(i)$。因此把询问拆成 $\sum_{i=1}^{R}f(i)-\sum_{i=1}^{L-1}f(i)$ 后询问复杂度为 $O(1)$。

然后再考虑预处理部分的复杂度，因为 $\varphi(x) \leq x$，考虑将 $x_0$ 初值设为 $B$，在 $x_0$ 满足 $\varphi(x_0)>B$ 前不断进行 $x_0 \gets x_0+1$ 的操作。这里又发现如果存在一个素数 $p$ 满足 $p>B+1$，$\varphi(p)=p-1>B$。因此 $x_0$ 增加的次数不会超过 $1e9$ 以内的最大素数距离。类似地，$k$ 的数值不会超过 $1e9$ 以内的最大素数距离 $+2 \log n$。打表得 $k \leq 500$。由于求 $\varphi(n)$ 的复杂度为 $O(\sqrt n)$，函数嵌套的次数不大于 $2 \log n$，因此预处理的总复杂度为 $O(k \sqrt n \log n)$。

总复杂度为 $O(k \sqrt n \log n+T)$，远远跑不满，可以通过本题。

贴一个代码

#include<bits/stdc++.h>
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define DU double
#define rep(i,x,n) for(int i=(x);i<=(n);i++)
#define nep(i,x,n) for(int i=(x);i>=(n);i--)
using namespace std;
const int N=1e5+10;
int T,B,lim,st[N],pr[N],phi[N],cntp;
ll s[N],tot;
unordered_map<int,int>p;
inline int read(){
	int s=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		s=(s<<3)+(s<<1)+(ch^48);
		ch=getchar();
	}
	return s*f;
}
inline void print(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
inline void initp(){
	st[1]=1,phi[1]=1;
	rep(i,2,1e5){
		if(!st[i]) pr[++cntp]=i,phi[i]=i-1;
		for(int j=1;i*pr[j]<=1e5;j++){
			st[i*pr[j]]=1;
			if(i%pr[j]==0){phi[i*pr[j]]=phi[i]*pr[j];break;}
			phi[i*pr[j]]=phi[i]*(pr[j]-1);
		}
	}
}
inline int Phi(int x){
	if(x<=1e5) return phi[x];
	if(p[x]) return p[x];
	int res=x;
	rep(i,1,cntp){
		if(pr[i]>x/pr[i]) break;
		if(x%pr[i]==0){
			res=res/pr[i]*(pr[i]-1);
			while(x%pr[i]==0) x/=pr[i];
		}
	}
	if(x>1) res=res/x*(x-1);
	return p[x]=res;
}
inline int getp(int u,int x){
	if(u<=0) return x;
	if(x==1) return x;
	return getp(u-1,Phi(x));
}
inline void init(){
	int now=B;
	while(Phi(now)<=B&&now<=1e9) now++;
	lim=now-1;
}
inline void initb(){
	for(int i=lim+1,now=Phi(lim);i<=1e9;i++){
		now=max(now,Phi(i));
		if(now>=B+60) break;
		s[i-lim]=s[i-lim-1]+getp(now-B,i),tot++;
	}
}
inline ll getans(int x){
	if(x==0) return 0;
	if(x<=lim) return (ll)x*(x+1)/2;
	if(x>lim+tot) return (ll)lim*(lim+1)/2+(x-(lim+tot))+s[tot];
	return (ll)lim*(lim+1)/2+s[x-lim];
}
inline void Solve(){
	T=read(),B=read();initp();init();initb();
	rep(i,1,T){
		int x=read(),y=read();
		print(getans(y)-getans(x-1)),puts("");
	}
}
int main(){
	int Tests=1;
	while(Tests--) Solve();
	return 0;
}