#include<stdio.h>

#define plm long long
#define Dmax 128
#define Mmax 78505
#define Pmax 1000001

int p[Mmax];
int t,A,B,d[Dmax];
bool e[Pmax];
plm nr_tot,cur,prod,sol,cnt;

void ciur()
{
    for(int i=2;i<Pmax;++i)
        if (!e[i])
            {
            p[++p[0]]=i;
            for(int j=2*i;j<Pmax;j+=i)
                e[j]=1;
            }
    
}

int primi(int x)
{
    d[0]=0;
    sol=0;
    
    for(int i=1;p[i]*p[i]<=x;++i)
        if (x%p[i]==0)
        {
        d[++d[0]]=p[i];
        for(;x%p[i]==0; x/=p[i]);
        }
    if (x>1)
        d[++d[0]]=x;
        
    nr_tot=(1<<d[0]);
    for(plm i=1;i<nr_tot;++i)
        {
            cur=i;
            prod=1;
            cnt=0;
            for(int j=1;cur;cur/=2 , ++j)
                if (cur%2==1)   
                    {
                    prod=prod*d[j];
                    cnt=(cnt+1)%2;
                    }
                    
            sol+= (cnt*2-1)*(A/prod);
        }
        
    return sol;
}

int main()
{
    ciur();
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%d",&t);
    for(;t;--t)
        {
        scanf("%d%d",&A,&B);
        printf("%d\n",A-primi(B));
        }
    return 0;
}