真的恶心....
#include<stdio.h>
int num[3000109];
long long c [3000109];
/*
3
1 6
1 100
1 1000000
*/
const int p=3000009;
int main()
{int t;scanf("%d",&t);c[1]=1;for(int i=2;i<p;i++){if(c[i]==0){for(int j=i;j<p;j+=i){if(c[j]==0) c[j]=j;c[j]=c[j]/i*(i-1);} }c[i]+=c[i-1];}while(t--){int a,b;scanf("%d %d",&a,&b);printf("%lld\n",c[b]-c[a-1]); } return 0;
}