Untitled

#include <bits/stdc++.h>
using namespace std ;
#define ll long long 
#define For(n) for(int i = 0; i < n; i++)
#define endl '\n'
const  int mx = 2000001;
bool isPrime (int n)
{
    if (n == 2) return true;
    if (n < 2 || n%2 == 0) return false;
    for (ll i = 3; i*i <= n; i+=2)
        if(n%i == 0) return false;
    return true;
}  
vector<ll> primestoN(int n)
{
    vector<ll> primes;
    primes.push_back(2);
    for (ll i = 3;i*i <= n*n; i+=2)
        if(isPrime(i))
                primes.push_back(i);
    return primes;
}
int sum[mx]{};//2 3 5 7 11 13
void solve ()
{
    vector<ll>primes = primestoN(mx);
    for (int i = 0; i <primes.size(); i++)
        for (size_t j = i; primes[j]*primes[i] < mx; j++)
            sum[primes[j]*primes[i]] = 1; 
     for(int i = 1; i <mx ;i++) sum[i] += sum[i-1];                  
// For(10) cout << sum[i]<< ' ';
int q;cin>>q;            
while (q--)
{
    int l,r;cin>>l>>r;
    cout << sum[r] - sum[l-1] << endl;
}
 
 
}
 
signed main ()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
// cin>>t;
while(t--)
{ 
    solve();
} 
    return 0;    
}