#include <fstream>
#define max 1000000
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
void ciur(int v[max], 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[max],m,i,k;
f>>m;
for(i=1; i<=m; i++)
{
f>>a>>b;
ciur(v,a,b,k);
g<<k<<'\n';
}
return 0;
}