#include<cstdio>
#include<cmath>
bool c[1000005];
int prime[100005];
void ciur()
{
    c[0]=c[1]=1;
    int n=1000000,i,j;
    int lim=(int)sqrt((double)n);
    for(i=4;i<=n;i=i+2)
        c[i]=1;
    for(i=3;i<=lim;i=i+2)
        if(!c[i])
            for(j=i*i;j<=n;j=j+2*i)
                c[j]=1;
    int u=0;
    for(i=2;i<=n;i++)
        if(!c[i])
            prime[++u]=i;
}
int u2;
long long fact[20];
void descfactpr(long long n)
{
    int d=1;
    u2=0;
    while(n>1 && prime[d]*prime[d]<=n)
      {
      bool ok=0;
      while(n%prime[d]==0)
        {
        n=n/prime[d];
        ok=1;
        }
      if (ok)
          fact[++u2]=prime[d];
      d++;
      }
    if (n>1)
        fact[++u2]=n;
}
long long pinex(long long x)
{
    long long ans=0;
    int i;
    int ns=1<<u2;
    for(i=1;i<ns;i++)
        {
        int c=i;
        long long p=1;
        int nr=1,cardinal=0;
        while(c)
          {
          if (c&1)
              {
              p=p*fact[nr];
              cardinal++;
              }
          nr++;
          c=c>>1;
          }
        if (cardinal%2==0)
            ans=ans-x/p;
        else
            ans=ans+x/p;
    }
    ans=x-ans;
    return ans;
}
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    int m,i;
    long long a,b;
    scanf("%d",&m);
    ciur();
    for(i=1;i<=m;i++)
        {
        scanf("%lld%lld",&a,&b);
        descfactpr(b);
        printf("%lld\n",pinex(a));
        }
return 0;
}