#include<cstdio>
using namespace std;
const int LIM=1000000, LIMC = 1000010, F=80010;
char ciur[LIMC]; long long nr;
void genCiur(){
    int d=2;
    while(d*d<=LIM){
        for(int i=2; i*d<=LIM; i++)
            ciur[i*d]=1;
        d++;
        while(ciur[d]==1) d++;
}
}
long long fact[F], a, b; int fn=0;
void decomp(long long x){
    long long d=2;
    while(x>1){
        while(x%d!=0||ciur[d]==1){
            d++;
        }
        if(d*d>x&&x>1){
            fn++; fact[fn]=d; x=1;
        }else{
        while(x%d==0)
            x/=d;
        fn++; fact[fn]=d;
        d++;}
    }
}
void scad(){
    long long temp=1;
    if(fn==0) return;
    if(fn==1){
        nr-=a/fact[1];
    }else
    if(fn==2){
        nr-=(a/fact[1]+a/fact[2]);
        nr+=a/(fact[1]*fact[2]);
    }else{
    for(int i=1; i<=fn; i++){
        nr-=a/fact[i];
        for(int j=i+1; i<fn && j<=fn; j++){
            nr+=a/(fact[i]*fact[j]);
        }
        temp*=fact[i];
    }
    nr-=a/temp;
    }
}
int main(){
    FILE *in=fopen("pinex.in","r"), *out=fopen("pinex.out","w");
    int n;
    fscanf(in, "%d", &n);
    genCiur();
    for(int i=1; i<=n; i++){
        fscanf(in, "%lld %lld", &a, &b);
        nr=a; fn=0;
        decomp(b);
        scad();
        fprintf(out, "%lld\n", nr);
    }
    return 0;
}