#include <fstream>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
void ciur(int v[1001], int a,int b, int &k)
{
    int i,j;
    for(i=1; i<=a; i++) v[i]=0;
    for(i=2; i<=b; i++)
    {
        if(v[i]==0&& b%i==0)
        for(j=i; j<=a; j+=i)
            v[j]=1;
    }
        k=0;
    for(i=1; i<=a; i++) if(v[i]==0) k++;
}
int main()
{
    int a,b,v[1001],m,i,k;
    f>>m;
    for(i=1; i<=m; i++)
    {
        f>>a>>b;
        ciur(v,a,b,k);
        g<<k<<'\n';
    }
    return 0;
}