#include<cstdio>
using namespace std;
int M,F[50],f,i,j,K,cnt;
long long A,B,Nr,Sol;
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%d",&M);
    for(;M;M--)
    {
        scanf("%lld%lld",&A,&B); f=0;
        if(B%2==0)
        {
            F[++f]=2;
            while(B%2==0) B/=2;
        }
        for(i=3;i*i<=B;i+=2)
            if(B%i==0)
            {
                F[++f]=i;
                while(B%i==0) B/=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;
}