#include<iostream>
#include<fstream>
#include<math.h>
using namespace std;
int nr[2000003];

    long long 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]==0)
        {
            for(long long i=j*j;i<1000000;i=i+j)
                    nr[i]=1;
            prime[numar]=j;
            numar++;
        }

    ifstream f("pinex.in");
    ofstream g("pinex.out");
    int n;
    f>>n;

    while(n)
    {
        nrfin=0;
        long long a,b;
        f>>a>>b;

        long long 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(long long i=1;i<lim;i++)
      { long semn=0;
      long long rr=1;
                for(long long 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;

      }

      g<<a-rez<<"\n";
    n--;
    }



}