#include <fstream>
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
const int dim=1e6;
int t,nrp[100000],d[100],p;
long long a,b,s,val;
bool ciur[dim+2];
void back(int k,int last){
    if(k==d[0]+1){
        if(d[0]%2==0)
            s-=a/val;
        else
            s+=a/val;
    }else{
        if(k!=1){
            if((k-1)%2==0)
                s-=a/val;
            else
                s+=a/val;
        }
        for(int i=last+1;i<=d[0];i++){
            val*=d[i];
            back(k+1,i);
            val/=d[i];
        }
    }
}
int main()
{
    ciur[0]=ciur[1]=1;
    for(int i=2;i<=dim;i++)
        if(ciur[i]==0){
            nrp[++p]=i;
            for(int j=2*i;j<=dim;j+=i)
                ciur[j]=1;
        }
    cin>>t;
    while(t--){
        cin>>a>>b;
        d[0]=0;
        if(b==1){
            cout<<a<<'\n';
            continue;
        }
        for(int i=1;i<=p&&1LL*nrp[i]*nrp[i]<=b;i++)
            if(b%nrp[i]==0){
                d[++d[0]]=nrp[i];
                while(b%nrp[i]==0)
                    b/=nrp[i];
            }
        if(b!=1)
            d[++d[0]]=b;
        s=0;
        val=1;
        back(1,0);
        cout<<a-s<<'\n';
    }
    return 0;
}