#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)
{
    if(y < 2)
    {
        //std::cout<<": "<<x<<'\n';
        fout<<x<<'\n';
        return;
    }
    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++;
    }
    if(myPrim.back() != y)
    {
        myPrim.push_back(y);
    }

//    bool myp[x];
//
//    for(int k = 0; k <= x; k++)
//    {
//        myp[k] = false;
//    }
    int nr = 0;
    for(int k = 0; k < myPrim.size(); k++)
    {
//        std::cout<<myPrim[k]<<' ';
        int j = myPrim[k];
        while(j <= x)
        {
            nr++;
//            std::cout<<j<<' ';
//            myp[j] = true;
            j += myPrim[k];
        }
    }
    int sum = x - nr;
//    for(int k = 1; k <= x; k++)
//    {
//        if(myp[k] != true)
//        {
////            sum++;
////            std::cout<<k<<' ';
//        }
//    }
    myPrim.clear();
//    std::cout<<": "<<sum<<'\n';
    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;
}