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

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
bool prim[MAXNR];
ll 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){
    ll nrd=0,rez=0;
    bool neprim=false;
    for(int i=1;b>1;i++){
        if(b%np[i]==0){
            nd[++nrd]=np[i];
            while(b%np[i]==0)
                b/=np[i];
        }
        if(np[i]*np[i]>b and b>1){
            nd[++nrd]=b;
            b=1;
        }
    }
    for(ll i=1;i<(1<<nrd);i++){
        ll auxi=i,h=nrd,nr=1,pi=0;
        while(auxi>0){
            if(auxi%2==1) nr=1LL*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;
}