#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int SS=0,WW=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
	{
        if(ch=='-')WW=-1;
        ch = getchar();
    }
    while(ch>='0'&&ch<='9')
	{
        SS=(SS<<1)+(SS<<3)+(ch^48);
        ch=getchar();
    }
    return SS*WW;
}
inline void write(int XX)
{
    if(XX<0)putchar('-'),XX=-XX;
    if(XX>9)write(XX/10);
    putchar(XX% 10 + '0');
}
const long long maxn=10000000;
int q;
int z[maxn+100];
int p[10000005],ind,l,r,mp[maxn+100],s[maxn+100];
void init()
{
	for(int i=2;i<=maxn;i++)
    {
    	if(!z[i])p[++ind]=i,mp[i]=i;
        for(int j=1;j<=ind&&i*p[j]<=maxn;j++)
        {
        	z[i*p[j]]=1,mp[i*p[j]]=mp[i];
            if(i%p[j]==0)
            break;
        }
    }
    for(int i=1;i<=maxn;i++)
    {
    	s[i]=s[i-1];
    	if(mp[i]*mp[i]>i)s[i]=s[i]+1;
	}
}
signed main()
{
	freopen("find.in","r",stdin);
	freopen("find.out","w",stdout);
	q=read();
	init();
    for(int i=1;i<=q;i++)
        l=read(),r=read(),write(s[r]-s[l-1]),puts("");
    return 0;
}

为什么把int改成long long会影响输出