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

using namespace std;

#define MXPRIM 1000000

int prime[MXPRIM / 10];
long long T, A, B, fact[30];
bool prim[MXPRIM];

void Ciur() {
    prim[0] = prim[1] = true;

    for(long long i = 2; i < MXPRIM; ++i)
        if(!prim[i]) {
            for(long long j = i * i; j < MXPRIM; j += i) {
                prim[j] = true;
            }

            prime[++prime[0]] = i;
        }
}

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

    Ciur();

    scanf("%lld", &T);
    for (int i = 1; i <= T; i++) {
        scanf("%lld %lld", &A, &B);

        long long t = 0, d = 1;

        while(B > 1) {
            if (B % prime[d] == 0) {
                fact[++t] = prime[d];
                while(B % prime[d] == 0) {
                    B /= prime[d];
                }
            }

            ++d;
        }

        long long sol = A;
        long long fnal = (1 << t);

        for(int i = 1; i < fnal; ++i) {
            long long nr = 0, prod = 1;

            for(int j = 0; j < t; ++j)
                if((1 << j) & i) {
                    prod = 1LL * prod * fact[j + 1];
                    ++nr;
                }

            if(nr % 2 == 1) nr = -1;
            else nr = 1;

            sol = sol + 1LL * nr * A / prod;
        }

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

    return 0;
}