#include <fstream>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int i,j,t;
bool ciur[1001*1001];
int diviz,a,b,k=0,d[100001],v[10000001];
void CIUR()
{
    int i,j;
    ciur[0]=ciur[1]=1;

    for(i=2;i*i<=1000000;i++)
        if(!ciur[i])
            for(j=i*2;j<=1000000;j+=i)
                ciur[j]=1;

    for(i=2;i<=1000000;i++)
        if(!ciur[i])
        {

            v[++k]=i;
        }

}
void desc(){
int i=2,cnt=1;
while(b!=1){

    if(b%v[cnt]==0)
    {d[++diviz]=v[cnt];
    while(!(b%v[cnt])) b/=v[cnt];

    }

    cnt++;

}



}
int cmmmc(int a,int b){
int q=a,p=b,r;
r=a%b;
while(b){
  r=a%b;
  a=b;
  b=r;


}
return (q*p)/a;

}
int main()
{f>>t;
CIUR();


for(k=1;k<=t;k++){
f>>a>>b;
int s=0,cc=b;
diviz=0;
desc();
int n=diviz;
int nr=0,sol=1;
for(i=1;i<(1<<n);i++){
        nr=0;sol=1;
for(j=0;j<n;j++){
    if(i&(1<<j)){
       nr++;
   sol=cmmmc(sol,d[j+1]);


    }



}
if(nr%2==1) s+=a/sol;
else s-=a/sol;

}
g<<a-s<<'\n';
}





    return 0;
}