#include <stdio.h>
#include <vector>
#define MAXSQRTB 1000005
using namespace std;

int nrt;
long long a, b;
bool nPrime[MAXSQRTB];
vector<int> primes;

void sieve() {
    for(int i = 2; i < MAXSQRTB; i++)
        if(!nPrime[i]) {
            primes.push_back(i);
            for(long long j = 1LL * i * i; j < MAXSQRTB; j += i)
                nPrime[j] = 1;
        }
}

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

    sieve();
    scanf("%d", &nrt);
    while(nrt--) {
        scanf("%lld %lld", &a, &b);

        vector<long long> desc;
        for(auto p: primes) {
            if(1LL * p * p > b) break;
            if(b % p == 0) {
                desc.push_back(p);
                while(b % p == 0) b /= p;
            }
        }
        if(b > 1) desc.push_back(b);

        long long sol = 0;
        int n = desc.size();

        for(int i = 0; i < (1 << n); i++) {
            int sign = 1;
            long long x = 1;
            for(int j = 0; j < n; j++)
                if(i & (1 << j)) {
                    sign = -sign;
                    x *= desc[j];
                }
            sol += sign * (a / x);
        }

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

    return 0;
}