#include <bits/stdc++.h>
#define MILION 1000000
using namespace std;

vector<unsigned int> numere_prime;
vector<bool> numere(MILION + 1, true);


void fill_numere_prime(){

    for(unsigned int i=2; i<=MILION; i++){

        if(numere[i]==true){
            numere_prime.push_back(i);

            for(int j=2*i; j<=MILION; j=j+i)
                numere[i] = false;
        }
    }
}



unsigned long long solve_pinex(unsigned long long A, unsigned long long B){

    vector<unsigned int> factori_B;
    unsigned int it = 0;
    while(B>1){

        if(B%numere_prime[it] == 0){

            factori_B.push_back(numere_prime[it]);

            while(B%numere_prime[it] == 0){
                B = B/numere_prime[it];
            }
        }

        it++;
    }

    unsigned long long solutie = 0;

    for(unsigned long long i=1; i<(1<<factori_B.size()); i++){

        unsigned long long produs=1;
        long long semn = 0;

        for(unsigned long long j=0; j<factori_B.size(); j++){
            if((1<<j)&i){
                produs = produs * factori_B[j];
                semn++;
            }
        }

        if(semn%2==0) semn=-1;
        else semn = 1;

        solutie = solutie + semn*(A/produs);
    }

    return A - solutie;
}

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

    fill_numere_prime();    //precalculăm numere prime

    unsigned short M;
    unsigned long long A, B;

    fin>>M;

    for(unsigned short i=1; i<=M; i++){
        fin>>A>>B;

        fout<<solve_pinex(A, B)<<endl;
    }
}