#include<stdio.h>

#define Dmax 128

int t,a,b,d[Dmax],sol;
int st[Dmax],v[Dmax],sum[Dmax];

void add(int k)
{
    sol=sol + ((k%2)*2-1)*(a/sum[k]);
}

void back(int k)
{
    for(int i=st[k-1]+1;i<=d[0];++i)
        {
        st[k]=i;
        if (v[i]!=1)
            {
            sum[k]=sum[k-1]*d[i];
            add(k);
            
            ++v[i];
            
            back(k+1);
            
            --v[i];
            }
        }
}

void primi(int x)
{
    for(int i=2;x>1;++i)
        if (x%i==0)
            {
            for (;x%i==0;x/=i);
            d[++d[0]]=i;
            }
}

int main()
{
    sum[0]=1;
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%d",&t);
    for(;t;--t)
        {
        scanf("%d%d",&a,&b);
        d[0]=0;
        sol=0;
        primi(b);
        back(1);
        printf("%d\n",a-sol);
        }
    return 0;
}