#include<iostream>
#include<fstream>
using namespace std;
int nr[1000001];
    int prime[80000];
    int divpr[40000];
    int numar;
    int nrfin=0;
int main()
{
        for(long j=2;j<1000000;j++)
        if(nr[j]==0)
        {
            for(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;
        int a,b;
        f>>a>>b;
        for(long i=0;i<numar;i++)
        if(b%prime[i]==0&&prime[i]<a)
        {divpr[nrfin]=prime[i];
        nrfin++;}
       int lim=1<<nrfin;
       int rez=0;

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



}