#include<iostream>
#include<string>

using namespace std;

#define LL long long
#define PM 100005
#define FM 1000005

int primes[PM],dim,c[105];
char mk[FM];

int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    
    int M;
    LL A,B;
    
    mk[1]=1;
    
    for(int i=2;i<1000000;++i)
      if(!mk[i])
      {
        primes[++dim]=i;
        for(int j=2*i;j<=1000000;j+=i)
          mk[j]=1;
      }
    
    scanf("%d",&M);
    
    while(M--)
    {
      scanf("%I64d %I64d",&A,&B);     
      
      int dc=0,ind=1;
      
      while(ind<=dim && B>1)
      {
        if(B%primes[ind]==0)
        {
          c[++dc]=primes[ind];
          while(B%primes[ind]==0) B/=primes[ind];
        }             
                     
        ++ind;
      }
      
      if(B!=1) c[++dc]=B;
      
      /*
      printf("%d\n",dc);
      
      for(int i=1;i<=dc;++i)
        printf("%d ",c[i]);
      
      printf("\n");    
      */
      
      LL ans=0;
      
      for(int i=1;i<(1<<dc);++i)
      {
        LL prd=1;
        
        int par=0;
        
        for(int j=0;j<dc;++j)
          if((1<<j)&i)
          {
            ++par;
            prd*=c[j+1];
          }
        
        if(par%2) ans+=(A/prd);
        else ans-=(A/prd);  
      }
      
      printf("%I64d\n",A-ans);
    }
    
    return 0;
}