#include <iostream> #include <cstring> #include <cmath> #include <algorithm> using namespace std ; const int M =1e6+33; #define int long long int b[M],c[M],tot; int s[M] ; void init(int top){ memset(b,1,sizeof b); b[1]=0; int i,j; for(i=2;i<=top;i++){ if(b[i]) c[++tot]=i; for(j=1;j<=tot&&i*c[j]<=top;j++){ b[i*c[j]]=0; if(i%c[j]==0) break; } } } signed main(){ init(1e6); int x,y,tes ; cin>>tes; while(tes--){ int ans =0; cin>>x>>y; for(int i=1;i<=tot;i++) for(int j=c[i]*c[i];j<=y;j*=c[i]) if(j>=x) ans++; cout<<ans<<'\n'; } }