#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int main()
{long long a,b,n,i,j,k,u,t,p,r;
fin>>n;
   for(u=1;u<=n;u++){
        fin>>a>>b;
        int v[100000]={0};
        t=1;
        p=0;
    for(i=2;i<=b;i++){
            if(i*i>=b && t==1){
            p=1;
            break;}
        if(b%i==0){
while(b%i==0)
    b=b/i;
v[t]=i;
t++;
}}
if(p==1){
    if(sqrt(b)*sqrt(b)==b){
        if(sqrt(b)<a)
            fout<<a-2<<"\n";
        else
            fout<<a-1<<"\n";
    }
    else{
             if(b<a)
            fout<<a-2<<"\n";
        else
            fout<<a-1<<"\n";
    }
}

else{
p=v[1];
r=a/v[1];
k=0;
t--;
for(i=2;i<=t;i++){
k=0;
    for(j=1;j<=i-1;j++)
    k=k+((a/v[i])/v[j]);
    if(i==2)
r=r+a/v[i]-k;
else
    r=r+a/v[i]-k+((a/v[i])/p);
p=p*v[i];}
fout<<a-r<<"\n";}}
    return 0;
}