#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 scanForBits(){
    unsigned long long shift=1, x=1, l=1<<fn;
    long long k; int g;
    while(x<l){
        k=1; g=0;
        for(int i=0; i<=63; i++){
            if((x&(shift<<i))!=0){
                k*=fact[i+1]; g++;
            }
        }
        if(g%2!=0)
            nr+=a/k;
        else nr-=a/k;
        x++;
    }
}
void decomp(long long b) {
    int d=2, p;
    while (b > 1) {
        p=0;
        while(b%d==0) {
            b=b/d;
            p++;
            }
        if(p!=0) {
            fn++;
            fact[fn]=d;
            }

        if ((d+1) *(d+1) > b && b > 1) {
            fact[++fn] = b;
            b = 1;

            }
        else {

            d++;
            while(ciur[d]==1)
                d++;
            }
        }

    }
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=0;
        fn=0;
        decomp(b);
        scanForBits();
        fprintf(out, "%lld\n", a-nr);
        }
    return 0;
}