#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

long long f[35];

void desc(long long n) {
    long long e, d, lim;
    lim = (long long) sqrt((double) n);
    d = 2;
    f[0] = 0;
    //memset(f, 0, sizeof(f));
    while(d <= lim && n > 1) {
        e = 0;
        while(n % d == 0) {
            ++ e;
            n /= d;
        }
        if(e != 0) {
            ++ f[0];
            f[f[0]] = d;
        }
        ++ d;
    }
    if(n > 1) {
        ++ f[0];
        f[f[0]] = n;
    }
}

long long sol(long long a, long long b) {
    long long n = 0, cate, prod, m;
    desc(b);
    m = 1 << f[0];

    for(long long i = 1; i < m; ++ i) {
        cate = 0;
        prod = 1;
        for(int j = 1; j <= f[0]; ++ j) {
            if(i & (1 << (j - 1))) {
                ++ cate;
                prod *= f[j];
            }
        }
        if(cate & 1) {
            n += a / prod;
        } else {
            n -= a / prod;
        }
    }

    return a - n;
}

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

    int n;
    long long a, b;
    scanf("%d", &n);

    for(int i = 1; i <= n; ++ i) {
        scanf("%lld%lld", &a, &b);
        printf("%lld\n", sol(a, b));
    }

    return 0;
}