#include <iostream>
#include <fstream>
#include <math.h>
#include <vector>
#define Bmax 1000005

using namespace std;

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

int P[Bmax],C[Bmax],X[Bmax];
long long A,B,S,M,k,N;
vector <long long> D;

void ciur(){
    for(int i=2;i<Bmax;i++){
        if(!C[i]){
            P[++k] = i;
            for(int j=2*i;j<=Bmax;j+=i){
                C[j]=1;
            }
        }
    }
    P[++k] = Bmax;
}

void desc(long long x){
    long long  L = 1+sqrt(x);
    for(int i=1;P[i]<=L;i++){
        if(!(x%P[i])){
            D.push_back(P[i]);
            while(!(x%P[i])){
                x/=P[i];
            }
        }
    }
    if(x>1) D.push_back(x);
    return;
}

void Back(int lvl){
    for(int i= X[lvl-1]+1;i<D.size();i++){
        X[lvl]=i;
        M *= D[i];
        if(lvl%2){
            S+=A/M;
        }
        else{
            S-=A/M;
        }
        if(lvl < D.size()){
            Back(lvl+1);
        }
        M/=D[i];
    }
}

void solve(long long A,long long B){
    D.clear();
    desc(B);
    M = 1;
    S = 0;
    Back(1);
    fout<<A-S<<"\n";
}

void read(){
    ciur();
    fin>>N;
    X[0]=-1;
    for(int g=1;g<=N;g++)
    {
        fin>>A>>B;
        solve(A,B);
    }
}



int main()
{
    read();
    return 0;
}