#include<cstdio>
#include<string>
#include<bitset>

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];
lld C[100005];
bitset<500005> viz;

void ciur() {
    int i, j, k;

    C[++cnt] = 2;

    for(i = 1, j = 3; j * j <= 1000000; i++, j += 2)
        if(!viz[i]) {
            C[++cnt] = j;
            for(k = j * j / 2; 2 * k + 1 <= 1000000; k += j)
                viz[k] = 1;
        }

    for(; j <= 1000000; i++, j += 2)
        if(!viz[i])
            C[++cnt] = j;
}

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

void decompose(lld B) {
    int i;

    for(i = 1; C[i]*C[i] <= B; i++)
        if(B % C[i] == 0) {
            P[++cnt] = C[i];
            while(B % C[i] == 0)
                B /= C[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);

    ciur();

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

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

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

    return 0;
}