#include<cstdio>
#include<bitset>
using namespace std;
const int PMAX = 1000000;
int M,F[50],f,i,j,K,cnt,P[PMAX/10],p;
long long A,B,Nr,Sol;
bitset<PMAX> viz;
void Citire()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%d",&M);
}
void Precalculare()
{
    P[++p]=2;
    for(i=3;i<PMAX;i+=2)
        if(!viz[i])
        {
            P[++p]=i;
            for(j=i*2;j<PMAX;j+=i) viz[j]=1;
        }
}
void Descompunere()
{
    scanf("%lld%lld",&A,&B); f=0;
    for(i=1;i<=p && P[i]*P[i]<=B;i++)
        if(B%P[i]==0)
        {
            F[++f]=P[i];
            while(B%P[i]==0) B/=P[i];
        }
    if(B>1) F[++f]=B;
}
void Reuniune()
{
    K=1<<f; Sol=0;
    for(i=1;i<K;i++)
    {
        cnt=0; Nr=1;
        for(j=0;j<f;j++)
            if((1<<j)&i) cnt++,Nr*=1LL*F[j+1];
        if(cnt&1) Sol+=A/Nr;
        else Sol-=A/Nr;
    }
    printf("%lld\n",A-Sol);
}
void Rezolvare()
{
    for(;M;M--)
    {
        Descompunere();
        Reuniune();
    }
}
int main()
{
    Citire();
    Precalculare();
    Rezolvare();
    return 0;
}