#include <iostream>
#include <fstream>
#include <vector>

std::ifstream fin("pinex.in");
std::ofstream fout("pinex.out");

int m, a[501], b[501];
bool primi[1000001];
std::vector<int> nrPrime;

void setPrimi()
{
    for(int i = 2; i < 1000001; i++)
    {
        primi[i] = true;
    }

    for(int i = 2; i < 1000001; i++)
    {
        if(primi[i])
        {
            nrPrime.push_back(i);

            int j = i + i;
            while(j < 1000001)
            {
                primi[j] = false;
                j += i;
            }
        }
    }
}

void citire()
{
    fin>>m;
    for(int i = 0; i < m; i++)
    {
        fin>>a[i]>>b[i];
        std::cout<<a[i]<<' '<<b[i]<<'\n';
    }
}

void check(int x, int y)
{
    std::vector<int> myPrim;
    for(int i = 0; i * i < y; i++)
    {
//        std::cout<<nrPrime[i]<<' ';
    }
//    std::cout<<'\n';
    int i = 0;
    while(nrPrime[i] < y)
    {
        if(!(y % nrPrime[i]))
        {
            myPrim.push_back(nrPrime[i]);
        }
        i++;
    }
    myPrim.push_back(y);
//    std::cout<<y<<' '<<myPrim.size()<<": ";
    for(int k = 0; k < myPrim.size(); k++)
    {
//        std::cout<<myPrim[k]<<' ';
    }

    bool myp[x];

    for(int k = 0; k < x; k++)
    {
        myp[k] = false;
    }
    for(int k = 0; k < myPrim.size(); k++)
    {
//        std::cout<<k<<' ';
        int j = myPrim[k];
        while(j < x)
        {
//            std::cout<<j<<' ';
            myp[j] = true;
            j += myPrim[k];
        }
    }
    int sum = 0;
    for(int k = 1; k < x; k++)
    {
        if(myp[k] != true)
        {
            sum++;
//            std::cout<<k<<' ';
        }
    }
    fout<<sum<<'\n';
}

void rezolvare()
{
    for(int i = 0; i < m; i++)
    {
//        std::cout<<a[i]<<' '<<b[i]<<": ";
        check(a[i], b[i]);
    }
}

int main()
{
    setPrimi();
    citire();
    rezolvare();
    return 0;
}