#include <stdio.h>
#define MAXK 11
#define MAXD 1000000
#define MAXQ 78498
int c[MAXD+1], v[MAXQ+1], d[MAXK];
inline void ciur(){
    int i, j, q;
    for(i=2; i*i<=MAXD; i++){
        if(c[i]==0){
            for(j=i*i; j<=MAXD; j+=i){
                c[j]=1;
            }
        }
    }
    q=0;
    for(i=2; i<=MAXD; i++){
        if(c[i]==0){
            v[q++]=i;
        }
    }
    //printf("%d\n", q);
}
inline int solve(int A, int n){
    int p, k, s, prod, nr, i, j;
    p=0;
    k=0;
    while(v[p]*v[p]<=n){
        if(n%v[p]==0){
            d[k++]=v[p];
            while(n%v[p]==0){
                n/=v[p];
            }
        }
        p++;
    }
    if(n!=1){
        d[k++]=n;
    }
    s=0;
    for(i=1; i<(1<<k); i++){
        nr=0;
        prod=1;
        for(j=0; (1<<j)<=i; j++){
            if(((1<<j)&i)!=0){
                nr++;
                prod*=d[j];
            }
        }
        if((nr&1)==0){
            s-=A/prod;
        }else{
            s+=A/prod;
        }
    }
    return A-s;
}
int main(){
    int T, t, A, B;
    FILE *fin, *fout;
    fin=fopen("pinex.in", "r");
    fout=fopen("pinex.out", "w");
    ciur();
    fscanf(fin, "%d", &T);
    for(t=0; t<T; t++){
        fscanf(fin, "%d%d", &A, &B);
        fprintf(fout, "%d\n", solve(A, B));
    }
    fclose(fin);
    fclose(fout);
    return 0;
}