#include <fstream>

using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int a, b, t, i, d, k, j, n, v[1001];
bool ok;
int main()
{
    f >> t;
    for(i=1;i<=t;i++)
    {
        f >> a >> b;
        n=0;
        for(d=1;d*d<=b;d++)
            if(b%d==0){
                v[++n]=d;
                v[++n]=b/d;
            }
        k=a;
        for(j=1;j<=a;j++){
            ok=1;
            for(d=2;d<=n&&ok==1;d++)
                if(j%v[d]==0) ok=0;
            if(ok==0) k--;
        }
        g << k << '\n';
    }
    return 0;
}