#include <iostream>
#include <cstdio>
#include <bitset>

using namespace std;

#define DIM 1000004

bitset <DIM> CE;
long long primes[DIM], fact[30];
void solve(long long, long long);
void Ciur();

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

    Ciur();

    long long A, B;
    cin >> A;

    while(cin >> A >> B) {
        solve(A, B);
    }

    return 0;
}

void Ciur() {
    CE[0] = CE[1] = 1;

    for(long long i = 2; i < DIM; ++i) {
        if(CE[i] == 0) {
            primes[++primes[0]] = i;
            for(long long j = i * i; j < DIM; j += i) {
                CE[j] = 1;
            }
        }
    }
}

void solve(long long A, long long B) {
    fact[0] = 0;
    long long ans = 0;
    for(int i = 1; i <= primes[0] && B > 1; ++i) {
        if(B % primes[i] == 0) {
            fact[++fact[0]] = primes[i];
        }

        while(B % primes[i] == 0) {
            B /= primes[i];
        }
    }

    if(B > 1) {
        fact[++fact[0]] = B;
    }

    for(int i = 1; i < (1 << fact[0]); ++i) {
        long long nrbiti = 0;
        long long prod = 1;

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

        if(nrbiti & 1) {
            nrbiti = 1;
        }
        else {
            nrbiti = -1;
        }

        ans = ans + nrbiti * A / prod;
    }

    cout << A - ans << '\n';
}