#include <cstdio>
#include <algorithm>

using namespace std;

int pw[15], np, v[15];
int primes[1000005], cp;
bool ciur[1000005];
long long sol, prod, A;

void sieve(){
    int i,j;
    for(i = 4;i <= 1000000;i += 2){
        ciur[i] = 1;
    }
    primes[++cp] = 2;
    for(i = 3;i <= 1000000;i += 2){
        if(ciur[i] == 0){
            primes[++cp] = i;
            if(1LL*i*i > 1000000){
                break;
            }
            for(j = i*i;j <= 1000000;j += i+i){
                ciur[j] = 1;
            }
        }
    }
}

void bkt(int step, const int& n){
    if(prod > A){
        return;
    }
    if(step == n+1){
        if(n&1){
            sol -= A/prod;
        }else{
            sol += A/prod;
        }
    }else{
        int i;
        for(i = v[step-1] + 1;i <= np;i++){
            v[step] = i;
            prod *= 1LL*pw[v[step]];
            bkt(step + 1, n);
            prod /= pw[v[step]];
        }
    }
}

int main(){
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    int test,q,i,j;
    long long B;
    scanf("%d", &q);
    sieve();
    for(test = 1;test <= q;test++){
        scanf("%lld %lld", &A, &B);
        sol = A;
        np = 0;
        for(i = 1;1LL*primes[i]*primes[i] <= B;i++){
            if(B%primes[i] == 0){
                pw[++np] = primes[i];
                while(B%primes[i] == 0){
                    B /= primes[i];
                }
            }
        }
        if(B != 1){
            pw[++np] = B;
        }
        for(i = 1;i <= np;i++){
            prod = 1;
            bkt(1, i);
        }
        printf("%lld\n", sol);
    }
    return 0;
}