#include<iostream>
#include<fstream>
#include<stdio.h>
#include<math.h>
using namespace std;
bool nr[1000003];

    int prime[80000];
    long long divpr[30];
    long long numar;
    long long nrfin=0;
int main()
{
        for(long long j=2;j<1000000;j++)
        if(nr[j]==false)
        {
            for(long long i=j*j;i<1000000;i=i+j)
                    nr[i]=true;
            prime[numar]=j;
            numar++;
        }

        FILE *f,*g;
        f=fopen("pinex.in","r");
        g=fopen("pinex.out","w");
        int n;
    fscanf(f,"%d",&n);

    while(n)
    {
        nrfin=0;
        long long a,b;
        fscanf(f,"%lld %lld",&a,&b);

        int i=0;
        while(b>1)
        {
            if(b%prime[i]==0)
            {
                divpr[nrfin]=prime[i];
                nrfin++;
                while(b%prime[i]==0)
                b=b/prime[i];
            }
            if(prime[i]>sqrt(b)&&b>1)
            {
                divpr[nrfin]=b;

                nrfin++;
                b=1;
            }
            i++;
        }
        long long lim=1<<nrfin;
       long long rez=0;
      for(int i=1;i<lim;i++)
      { int semn=0;
      long long rr=1;
                for(int j=0;j<nrfin;j++)
                if(i&(1<<j))
                {rr=rr*divpr[j];
                semn++;}

        if(semn%2==0)
        rez=rez-a/rr;
        else
        rez=rez+a/rr;

      }

      fprintf(g,"%lld\n",a-rez);
    n--;
    }



}