#include <bits/stdc++.h>

using namespace std;

unsigned int numere_prime[80000];
unsigned int factori_B[30];
bool numere[1000000+1];


void fill_numere_prime(){
    int k = -1;

    for(int i=0; i<=1000000; i++){
        numere[i] = true;
    }

    for(int i=2; i<=1000000; i++){
        if(numere[i]==true){
            numere_prime[++k] = i;

            for(int j=(i<<1); j<=1000000; j=j+i){
                numere[j] = false;
            }
        }
    }
}


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


    unsigned int it = 0;
    int k=-1;

    while(B>1){

        if(B%numere_prime[it] == 0){
            factori_B[++k] = numere_prime[it];

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

        if(numere_prime[it]>sqrt(B) && B>1){
            factori_B[++k] = B;
            B=1;
        }

        it++;
    }

    unsigned long long solutie = 0;

    for( int i=1; i<(1<<(k+1)); i++){

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

        for(int j=0; j<k+1; j++){
            if((1<<j)&i){
                produs = 1LL*produs * factori_B[j];
                semn++;
            }
        }

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

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

    return A - solutie;
}

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

    fill_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;
    }
}