#include <cstdio>
#include <vector>

using namespace std;

vector <long long> v, prim;
bool c[1000005];

void ciur() {
    int n = 1000000;
    for(int i = 4; i <= n; i += 2) {
        c[i] = 1;
    }
    c[0] = c[1] = 1;
    for(int i = 3; i <= 1000; i += 2) {
        if(!c[i])
            for(int j = i * i; j <= n; j += 2 * i)
                c[j] = 1;
    }
    prim.push_back(2);
    for(int i = 3; i <= n; ++ i) {
        if(!c[i])
            prim.push_back(i);
    }
}

void descompunere(long long a) {
    int e;
    long long d;
    d = 0;
    while(prim[d] * prim[d] <= a && a > 1) {
        e = 0;
        while(a % prim[d] == 0) {
            a /= prim[d];
            ++ e;
        }
        if(e > 0) {
            v.push_back(prim[d]);
        }
        ++ d;
    }
    if(a > 1) {
        v.push_back(a);
    }
}

long long solve(long long a, long long b) {
    descompunere(b);
    long long sub, mask, prod, rasp = 0;
    sub = 1 << v.size();
    for(long long i = 1; i < sub; ++ i) {
        prod = -1;
        for(int j = 0; j < v.size(); ++ j) {
            mask = 1 << j;
            if(i & mask) {
                prod *= -v[j];
            }
        }
        rasp += a / prod;
    }
    v.clear();
    return rasp;
}

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

    int t;
    long long a, b;
    ciur();

    scanf("%d", &t);

    while(t--) {
        scanf("%lld%lld", &a, &b);
        printf("%lld\n", a - solve(a, b));
    }

    return 0;
}