#include <iostream>
#include <fstream>
#include <bitset>
#include <cmath>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
long long n,a,b,k,v[1000003],x,rez;
bitset<1000003> c;
int main()
{
    for(int i=2;i<=1000;++i)
    {
        for(int j=2;j<=1000000/i;++j)
        {
            c[i*j]=1;
        }
    }
    c[1]=1;
    f>>n;
    for(int z=1;z<=n;++z)
    {
        f>>a>>b;
        x=sqrt(b);
        k=rez=0;
        for(int i=1;i<=b;++i)
        {
            if(c[i]==0 && b%i==0)
            {
                ++k;
                v[k]=i;
            }
        }
        for(int i=1;i<=a;++i)
        {
            for(int j=1;j<=k;++j)
            {
                if(i%v[j]==0)
                {
                    rez++;
                    break;
                }
            }
        }
        g<<a-rez<<'\n';
    }
    return 0;
}