#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
long long a,b,m,prime[100000],div[40],cateprime,j,i,l,d,catidiv,val,ci,aux,catecifre,sol;
bool ciur[1500100];

int main()
{
for( i=2;i<1000000;i++)
{
    if(ciur[i]==0)
    {
        prime[++cateprime]=i;
        for(j=i*2;j<1000000;j+=i)
            ciur[j]=1;
    }
}

f>>m;
for(l=1;l<=m;l++)
{
    f>>a>>b;
    a--;
    sol=0;
    val=1;
    catidiv=0;
    for(d=1;prime[d]*prime[d]<=b;d++)
    {
        if(b%prime[d]==0)
        {val=val*2;
            div[++catidiv]=prime[d];
            while(b%prime[d]==0) b=b/prime[d];

        }
    }
    if(b>1) {div[++catidiv]=b;val=val*2;}
    for(i=1;i<=val-1;i++)
    {
        ci=i;
        aux=1;
        catecifre=0;
        for(j=catidiv;j>=1;j--)
        {
            if(ci%2==1) {aux*=div[j];catecifre++;}
            ci/=2;
        }


if(catecifre%2==1) sol+=a/aux;
else sol-=a/aux;

    }
   g<<a-sol<<'\n';



}
}