#include <cstdio>

using namespace std;

const int nmx = 1000000;
const long long pow10_12 = 1000000;

int n;
long long A,B;
long long facb[20];
long long fac[nmx];

void factori(){
    fac[0] = 2;
    fac[1] = 2;
    fac[2] = 3;
    bool ok;
    for(long long i = 5; i <= pow10_12; i += 2){
        ok = 1;
        for(long long j = 1; ok && j <= fac[0] && fac[j] * fac[j] <= i; ++j)
            if(i % fac[j] == 0)
                ok = 0;
        if(ok)
            fac[++fac[0]] = i;
    }
}

void factori_B(){
    facb[0] = 0;
    for(int i = 1; i <= fac[0] && fac[i] <= B; ++i)
        if(B % fac[i] == 0)
            facb[++facb[0]] = fac[i];

}

int main(){
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);

    factori();

    scanf("%d", &n);

    int nrp = 0;
    long long t, total;
    for(int i = 1; i <= n; ++i){
        scanf("%lld %lld", &A, &B);
        factori_B();
        total = A;
        for(int nr = 1; nr <= (1 << facb[0]) - 1; ++nr){
            t = 1;
            nrp = 0;
            for(int k = 0; k < facb[0]; ++k)
                if(nr & (1 << k)){
                    ++ nrp;
                    t *= facb[k+1];
                }
            if(nrp % 2 == 1)
                total -= A / t;
            else
                total += A / t;
        }
        printf("%lld\n", total);
    }

    return 0;
}