#include <bits/stdc++.h>
using namespace std;
ifstream fin ("pinex.in");
ofstream fout ("pinex.out");
long long i,prime[100000],pr,divizori[50],dim,cnt,x[50],SOL,T,a,b;
bitset <1001010> f;
void ciur(){
    prime[++pr]=2;
      for(int i=3;i<=1001000;i+=2){
        if(f[i]==0)
            prime[++pr]=i;
        for(int j=i+i+i;j<=1001000;j+=(i<<1))
            f[j]=1;
      }
}
void factorizare(int el){
    int indice=1;
    int d=prime[indice];
    while(el!=1 && d*d<=el){
        if(el%d==0){
            divizori[++dim]=d;
            while(el%d==0)
                el/=d;
        }
        d=prime[++indice];
    }
    if(el!=1)
      divizori[++dim]=el;

}
void termen(){
    int produs=1;
    for(int i=1;i<=dim;i++)
        if(x[i])
            produs*=divizori[i];
    if(cnt%2==0)
        produs=-produs;
    if(produs!=1 && produs != -1)
    SOL+=(a/produs);

}
void btr(int n, int k){
   if(k>n)
        termen();
   else
        for(int i=0;i<=1;i++){
            x[k]=i;
            cnt+=i;
            btr(n,k+1);
            cnt-=i;
        }


}
int main(){
    ciur();
    fin>>T;
    while(T--){
        fin>>a>>b;
        dim=0;
        factorizare(b);
        SOL=0;
        btr(dim,1);
        fout<<a-SOL<<"\n";
    }

    return 0;
}