#include<cstdio>
#include<string>

using namespace std;

#ifdef HOME
const string inputFile = "input.txt";
const string outputFile = "output.txt";
#else
const string problemName = "pinex";
const string inputFile = problemName + ".in";
const string outputFile = problemName + ".out";
#endif

typedef long long int lld;

int N;
lld A, B, sol;
int cnt;
lld P[20];
int S[20];

void clear() {
    sol = A;
    cnt = 0;
}

void primes(lld B) {
    int i;

    for(i = 2; i * i <= B; i++)
        if(B % i == 0) {
            P[++cnt] = i;
            while(B % i == 0)
                B /= i;
        }

    if(B > 1)
        P[++cnt] = B;
}

void back(int top, lld div) {
    if(top > 1)
        sol += A / div;

    if(top > cnt)
        return;

    for(int i = S[top - 1] + 1; i <= cnt; i++) {
        S[top] = i;
        back(top + 1, -div * P[i]);
    }
}

int main() {
    freopen(inputFile.c_str(), "r", stdin);
    freopen(outputFile.c_str(), "w", stdout);

    scanf("%d", &N);

    while(N--) {
        scanf("%lld%lld", &A, &B);

        clear();
        primes(B);
        back(1, 1);

        printf("%lld\n", sol);
    }

    return 0;
}