#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;
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%d",&M); 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;
        }
    for(;M;M--)
    {
        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;
        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);
    }
    return 0;
}