#include <iostream>
#include <fstream>
#define ll long long
#define MAXNRDIV
#define MAXNR 1000001
#define MAXNRP 78499

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
bool prim[MAXNR];
int np[MAXNRP],nrp,nd[MAXNRP];
void ciur(){
    prim[1]=prim[0]=1;
    for(int i=2;i<MAXNR;i+=2){
        if(prim[i]==0){
            nrp++,np[nrp]=i;
            for(int d=2;d*i<MAXNR;d++) prim[d*i]=1;
        }
        if(i==2) i--;
    }
}
void solve(ll a,ll b){
    int nrd=0,rez=0;
    if(prim[b]==0) nrd++,nd[nrd]=b;
    else{
        for(int i=1;i<=nrp and np[i]<=b;i++){
            if(b%np[i]==0) nrd++,nd[nrd]=np[i];
        }
    }
    for(int i=1;i<(1<<nrd);i++){
        int auxi=i,h=nrd,nr=1,pi=0;
        while(auxi>0){
            if(auxi%2==1) nr*=nd[h],pi++;
            h--,auxi=auxi>>1;
        }
        if(pi%2==0) rez-=a/nr;
        else rez+=a/nr;
    }
    fout<<a-rez<<'\n';
}
int main(){
    ciur();
    int t;
    fin>>t;
    for(int i=1;i<=t;i++){
        ll a,b;
        fin>>a>>b;
        solve(a,b);
    }
    return 0;
}