#include<stdio.h>
char ciur[1000001];
int fact[80001];
int main(){
    long long i,k,j,n;
    long long a,b,f,d,prod,nr,p;
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%lld",&n);
    d=2;
    while(d*d<=1000000){
        for(i=2;i<=1000000/d;i++)
            ciur[i*d]=1;
        d++;
        while(ciur[d]==1)
            d++;
    }

    for(int k=1;k<=n;k++){

        scanf("%lld%lld",&a,&b);
        nr=0; prod=1;
        f = 0, d = 2;
        while (b > 1) {
            p=0;
            while(b%d==0){
                b=b/d;
                p++;
            }
            if(p!=0){
                f++;
                fact[f]=d;
                prod=prod*d;
            }
        if (d *d > b && b > 1) {
            fact[++f] = b;
            prod=prod*b;
            b = 1;

        }
        else{
            d++;
            while(ciur[d]==1)
                d++;
            }
        }
        if(f>2)
            nr=nr+a/prod;
        for(i=1;i<=f;i++){
            nr=nr+a/fact[i];
            if(i<=f-1)
                for(j=i+1;j<=f;j++)
                    nr=nr-(a/(fact[i]*fact[j]));
        }
        printf("%lld\n",a-nr);


        }
    return 0;
}