#include<stdio.h>
#include<math.h>
#define maxd 1000005
#define maxp 80000
using namespace std;
typedef long long ll;

int m,n,nr;
ll a,b,sol,prod;
int sieve[maxd],prime[maxp];
int v[maxp],x[maxp];

void preproc()
{
    int i,lim=maxd-5;

    prime[++nr]=2;
    for(i=3;i*i<=lim;i+=2)
     if(!sieve[i])
     {
         prime[++nr]=i;
         for(int j=i;i*j<=lim;j++)
          sieve[i*j]=1;
     }
     for(;i<=lim;i+=2)
      if(!sieve[i])
        prime[++nr]=i;

}

void back(int k,int sgn)
{
    if(k-1>0)  sol+=sgn*(a/prod);
    if(k>n) return;
    for(int i=x[k-1]+1;i<=n;i++)
    {
        x[k]=i;
        prod*=v[i];
        back(k+1,-sgn);
        prod/=v[i];
    }
}

void solve()
{
    ll q;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld",&a,&b);
        n=0; sol=0;
        q=sqrt(b);
        for(int j=1;prime[j]<=q && prime[j]<=a;j++)
        {
            if(b%prime[j]==0) v[++n]=prime[j];
            while(b%prime[j]==0) b/=prime[j];
        }
        if(b!=1) v[++n]=b;

        prod=1; back(1,-1);
        printf("%lld\n",a-sol);
    }
}

int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);

    preproc();
    solve();

    fclose(stdin);
    fclose(stdout);
    return 0;
}