#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 decomp(long long x) {
    long long d=2;
    while(x>1) {
        while(x%d!=0||ciur[d]==1) {
            d++;
            if(d*d>LIM){
                fn++; fact[fn]=d; return;
            }
        }
        if(d*d>x&&x>1) {
            fn++;
            fact[fn]=d;
            x=1;
            }
        else {
            while(x%d==0)
                x/=d;
            fn++;
            fact[fn]=d;
            d++;
            }
        }
    }*/
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++;
            }
        }

    }
void scad() {
    long long temp=1;
    if(fn==0) return;
    if(fn==1) {
        nr-=a/fact[1];
        }
    else if(fn==2) {
        nr-=(a/fact[1]+a/fact[2]);
        nr+=a/(fact[1]*fact[2]);
        }
    else {
        for(int i=1; i<=fn; i++) {
            nr-=a/fact[i];
            for(int j=i+1; i<fn && j<=fn; j++) {
                nr+=a/(fact[i]*fact[j]);
                }
            temp*=fact[i];
            }
        nr-=a/temp;
        }
    }
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=a;
        fn=0;
        decomp(b);
        scad();
        fprintf(out, "%lld\n", nr);
        }
    return 0;
    }