#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000001
#define MAXPRIME 100000
#define MAXDIV 20
char ciur[MAXN];
int prime[MAXPRIME],div1[MAXDIV];
inline int zeros(int nr){
    int con=0;
    while(nr){
        nr=(nr&(nr-1));
        con++;
    }
    return con;
}
int main(){
    FILE*fi,*fout;
    int i,j,d,n,m,x,e,nr,put,p2,p;
    long long s,a,b;
    fi=fopen("pinex.in" ,"r");
    fout=fopen("pinex.out" ,"w");
    fscanf(fi,"%d" ,&m);
    for(i=2;i*i<MAXN;i++)
       if(ciur[i]==0)
          for(j=i*i;j<=MAXN;j+=i)
             ciur[j]=1;
    n=0;
    for(i=2;i<MAXN;i++)
       if(ciur[i]==0)
           prime[n++]=i;
    for(i=0;i<m;i++){
        fscanf(fi,"%lld%lld" ,&a,&b);
        s=0;
        d=prime[0];
        j=1;
        x=0;
        while(d*d<=b){
            e=0;
            while(b%d==0){
                b/=d;
                e++;
            }
            if(e>0)
                div1[x++]=d;
            d=prime[j++];
        }
        if(b>1)
            div1[x++]=b;
        p2=(1<<x);
        for(j=1;j<p2;j++){
            nr=j;
            put=1;
            for(p=0;p<x;p++){
                if(nr%2==1)
                    put=put*div1[p];
                nr/=2;
            }
            if(zeros(j)%2==1)
                s+=(a/put);
            else
                s-=(a/put);
        }
        fprintf(fout,"%lld\n" ,a-s);
    }
    fclose(fi);
    fclose(fout);
    return 0;
}