#include
#include
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
while(t–)
{
int a,b;
cin>>a>>b;
int arr[b-a+1];
for(int i=a;i<=b;i++)
arr[i-a]=i;
if(a==1)
arr[0]=0;
for(int i=2;i<=b;i++)
{
int p=pow(i,2);
int j=0;
if(p<=b)
{
while(j<b-a+1)
{
if(arr[j]>=p && arr[j]%i==0)
{
arr[j]=0;
j+=i;
}
else
j++;
}
}
else
break;
}
int c=0;
for(int i=0;i<b-a+1;i++)
{
if(arr[i]!=0)
c++;
}
cout<<c<<endl;
}
}