#include <fstream>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long a,b,nr,n,sol,i,d,t,k,j,v[300010],w[50010];
int f[1000010],f1[50010],x[50010];
void bkt(int pas){
    sol=1;
    if(pas>1){
        if((pas-1)&1){
            for(int i=1;i<pas;i++)
                sol*=w[x[i]];
            nr-=(a/sol);
        }else{
            for(int i=1;i<pas;i++)
                sol*=w[x[i]];
            nr+=(a/sol);
        }
    }
    for(int i=x[pas-1]+1;i<=n;i++)
        if(f1[i]==0){
            f1[i]=1;
            x[pas]=i;
            bkt(pas+1);
            f1[i]=0;
        }
}
int main(){
    for(i=2;i<=1000000;i++)
        if(f[i]==0){
            v[++k]=i;
            for(j=i*2;j<=1000000;j+=i)
                f[j]=1;
        }
    fin>>t;
    for(;t--;){
        fin>>a>>b;
        n=0;
        d=1;
        while(v[d]<=b/v[d]&&b!=1&&d<=k){
            if(b%v[d]==0){
                w[++n]=v[d];
                while(b%v[d]==0)
                    b/=v[d];
            }
            d++;
        }
        if(b!=1)
            w[++n]=b;
        nr=a;
        bkt(1);
        fout<<nr<<"\n";
    }

    return 0;
}