#include<bits/stdc++.h>
#define MaxVal 1000000
using namespace std;
int st[105],f[105],prime[500005],dp,n,df;
long long sol,a,b;
bool ciur[MaxVal+5];
void op(int p)
{
    int nr=0;
    long long pr=1;
    for(int i=1;i<=p;i++)
    {
        nr=nr+st[i];
        if(st[i])
        {
            pr=pr*1LL*f[i];
        }
    }
    if(!nr) return;
    if((nr%2)) sol=sol+(a/pr);
        else sol=sol-(a/pr);
}
void bktr(int p,int n)
{
    for(int i=0;i<=1;i++)
    {
        st[p]=i;
        if(p==n) op(p);
            else
        if(p<n) bktr(p+1,n);
    }
}
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    for(int i=2;i<MaxVal;i++)
    {
        if(!ciur[i])
        {
            for(int j=(i<<1);j<=MaxVal;j+=i)
            {
                ciur[j]=1;
            }
        }
    }
    for(int i=2;i<=MaxVal;i++)
    {
        if(!ciur[i])
        {
            prime[++dp]=i;
        }
    }
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        sol=0;
        scanf("%lld%d",&a,&b);
        df=0;
        for(int j=1;j<=dp && (prime[j]*prime[j])<=b;j++)
        {
            if(!(b%prime[j]))
            {
                f[++df]=prime[j];
                while(b>1 && !(b%prime[j]))
                {
                    b/=prime[j];
                }
            }
        }
        if(b>1)
        {
            f[++df]=b;
        }
        bktr(1,df);
        printf("%lld\n",a-sol);
    }
    return 0;
}