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

    long long prime[80000];
    long long divpr[40000];
    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;
        for(long long i=0;i<numar;i++)
        if(b%prime[i]==0&&prime[i]<=a)
        {divpr[nrfin]=prime[i];
        nrfin++;}
        long long lim=0;
        if(nrfin)
        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;

      }
      if(rez==0&&lim==1)
      g<<a-1<<"\n";
      else
      if(rez==0&&lim==0)
      g<<a<<"\n";
      else
      g<<a-rez<<"\n";
    n--;
    }



}