#include <stdio.h>

#define NRDMAX 12
#define MAXVAL 1000000
#define NRPRIM 80000

int divprim[NRDMAX];
char ciur[MAXVAL];
int nrprime[NRPRIM];

void calcNrPrime(){
    int d, i, cnt;

    for(d = 2; d * d <= MAXVAL; d++){
        if(ciur[d] == 0){
            for(i = d * d; i <= MAXVAL; i += d){
                ciur[i] = 1;
            }
        }
    }

    cnt = 0;
    for(i = 2; i <= MAXVAL; i++){
        if(ciur[i] == 0){
            nrprime[cnt++] = i;
        }
    }
}

int main()
{
    FILE *fin, *fout;
    fin = fopen("pinex.in", "r");
    fout = fopen("pinex.out", "w");

    int m, i, d, e, nrd, bit, nrdiv;
    long long a, b, p, cnt, j;

    calcNrPrime();

    fscanf(fin, "%d", &m);

    for(i = 0; i < m; i++){
        fscanf(fin, "%lld%lld", &a, &b);
        nrd = 0;
        j = 0;
        d = nrprime[0];
        while(1LL * d * d <= b){
            e = 0;
            while(b % d == 0){
                b /= d;
                e++;
            }
            if(e > 0){
                divprim[nrd++] = d;
            }
            j++;
            d = nrprime[j];
        }
        if(b > 1){
            divprim[nrd++] = b;
        }
        cnt = 0;
        for(j = 1; j < (1LL << nrd); j++){
            p = 1;
            nrdiv = 0;
            for(bit = 0; bit < nrd; bit++){
                if(j & (1LL << bit)){
                    p *= divprim[bit];
                    nrdiv++;
                }
            }
            if(nrdiv & 1){
                cnt += a / p;
            }
            else{
                cnt -= a / p;
            }
        }
        fprintf(fout, "%lld\n", a - cnt);
    }

    fclose(fin);
    fclose(fout);
    return 0;
}