#include <cstdio>
#include <bitset>

using namespace std;

const int FACT=20;
const int PMAX=1000000;
const int NRPRIME=100000;

int term[FACT];
int prime[NRPRIME];

long long a,b,t,sol;

bitset <PMAX+5>ap;

void ciur(){
   prime[++prime[0]]=2;
   for (int i=3;i<=PMAX;i+=2)
   if (!ap[i]){
      prime[++prime[0]]=i;
      for (long long j=1LL*i*i;j<=PMAX;j+=i)
        ap[j]=1;
   }
}
int main()
{
   freopen("pinex.in","r",stdin);
   freopen("pinex.out","w",stdout);

   ciur();
   for (scanf("%lld\n",&t);t;t--){
      scanf("%lld %lld\n",&a,&b);

      term[0]=0;
      for (int i=1;i<=prime[0] && prime[i]*prime[i]<=b;i++)
        if (b%prime[i]==0){
          term[++term[0]]=prime[i];
          while (b%prime[i]==0)b/=prime[i];
        }
      if (b>1)term[++term[0]]=b;

      long long sol=0;
      for (int i=1;i<(1<<term[0]);i++){
         long long numar=1,prod=1,nr=1,p=1,semn=0;
         while (numar<=i){
            if (i&numar)semn++,prod*=term[p];
            numar<<=1;
            p++;
         }
         if (semn%2)sol+=a/prod;
         else sol-=a/prod;
      }
      printf("%lld\n",a-sol);
   }


   fclose(stdin);
   fclose(stdout);
}