TOPIC

#include <iostream>

using namespace std;
const int MAX = 1000000;
bool primos[MAX+1];

void criba()
{
    for(int i = 0; i<=MAX; i++) primos[i] = true;
    primos[0] = primos[1] = false;
    for(int i= 2; i <= MAX; i++)        if(primos[i])
        for(int j = i+1; j <= MAX; j = j+i)     primos[j] = false;
}

int main()
{
    criba();

    int a, b, n;
    cin >> n;

    while(n--)
    {
        cin >> a >> b;
        bool v[a+1];
        for(int i = 0; i <= a; i++) v[i]=true;
        v[0]=v[1]=false;

        for(int i = 2; i <= a; i++){
            if(!primos[i] and i<=b){
                for(int j = i+1; j<=a; j+=i)    v[j] = true;
            }else if(!primos[i] and i>b){
                //cout << "borrando para "<< i << endl;
                for(int j = i+1; j <= a; j+=i)  v[j] = false;
            }
        }
        int cont = 0;
        for(int i = 2; i <= a; i++)
            if(v[i])    cont++;
        cout << cont << endl;
    }
    return 0;
}