#include <fstream>
#include <vector>

using namespace std;

const int ValMax = 1e6;

vector<int> primes, factori;
bool ciur[ValMax + 5];

long long a;

long long pinex(){
    int cnt, len = factori.size();
    long long fact, sol;

    sol = 0;
    for(long long mask = 1; mask < (1 << len); mask++){
        cnt = 0;
        fact = 1;

        for(int i = 0; i < len; i++){
            if((mask & (1 << i))){
                cnt++;
                fact *= factori[i];
            }
        }

        if(cnt % 2 == 1){
            sol += (a / fact);
        }
        else{
            sol -= (a / fact);
        }
    }

    return sol;
}

int main(){
    ifstream fin("pinex.in");
    ofstream fout("pinex.out");

    int n;
    long long b;

    fin >> n;

    ciur[0] = 1;
    ciur[1] = 1;
    for(int i = 2; i <= ValMax; i++){
        if(!ciur[i]){
            primes.push_back(i);

            for(long long j = 1LL * i * i; j <= ValMax; j += i){
                ciur[j] = 1;
            }

        }
    }

    for(int i = 1; i <= n; i++){
        fin >> a >> b;

        for(unsigned int j = 0; j < primes.size() && primes[j] <= b; j++){
            if(b % primes[j] == 0){
                factori.push_back(primes[j]);

                while(b % primes[j] == 0){
                    b /= primes[j];
                }
            }
        }

        if(b > 1){
            factori.push_back(b);
        }

        fout << a - pinex() << '\n';

        factori.clear();
    }

    return 0;
}