#include <stdio.h>
#include <stdlib.h>
#define MAXDIV 100

int dvz[MAXDIV], ind;
int main(){
    int m, a, b, i, j;
    long long rez=0;
    FILE*fi,*fo;
    fi=fopen("algsort.in","r");
    fo=fopen("algsort.out","w");
    fscanf(fi,"%d", &m);
    for(i=0;i<m;i++){
        fscanf(fi,"%d%d", &a, &b);
        rez=0;
        ind=0;
        int d=2;
        while(d*d<=b){
            if(b%d==0){
                dvz[ind++]=d;
                while(b%d==0)
                    b/=d;
            }
            d++;
        }
        if(b>1)
            dvz[ind++]=b;
        for(j=1;j<(1<<ind);j++){
            int cj=j, nrbit=0, con=0, cmmmc=1;
            while(cj>0){
                if(cj%2==1){
                    nrbit++;
                    cmmmc=cmmmc*dvz[con];
                }
                con++;
                cj/=2;
            }
            if(nrbit%2==1)
                rez+=a/cmmmc;
            else
                rez-=a/cmmmc;
        }
        fprintf(fo,"%lld\n", (long long)a-rez);
    }
    fclose(fi);
    fclose(fo);
    return 0;
}