#include<fstream>
#include<cstring>
#define DIM (1<<20)
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long x[974935],v[274935],i,j,n,k,a,b,t,nr,bb;
char w[DIM+10],f[DIM];
long long sum,p;
void bk(){
    int nr1=0;
    while(f[0]!=1){
        i=n;
        while(f[i]==1){
            f[i]=0;
            i--;
        }
        f[i]=1;
        if (i == 0)
            break;
        nr1=0;
        p=1;
        for(j=1;j<=n;j++){
            if(f[j]==1){
                nr1++;
                p*=v[j]*1LL;
            }
        }
        k=1;
        if(nr1%2==0){
            k=-1;
        }
        sum+=(a/p)*k;
    }
    return ;
}
int main(){
    fin>>t;
    for(i=2;i<=DIM;i++){
        if(w[i]==0){
            x[++nr]=i;
            for(j=i+i;j<=DIM;j+=i){
                w[j]=1;
            }
        }
    }

    for(;t!=0;t--){
        fin>>a>>b;
        bb=b;
        n=0;
        for(i=1;x[i]*x[i]<=bb && b!=1;i++){
            if(b%x[i]==0){
                v[++n]=x[i];
                while(b%x[i]==0) b/=x[i];
            }
        }
        if(b!=1){
            v[++n]=b;
        }
        sum=0;
        memset(f,0,sizeof(f));
        bk();
        fout<<a-sum<<"\n";
    }
    return 0;
}