#include <bits/stdc++.h>

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

int Q,k,nrdiv,nr1;
long long a,b,Stot,s;
int nrprim[79000],x[22],divb[22];
bitset<1000005>ciur;

void CIUR()
{
    int i,j;
    ciur[0]=ciur[1]=1;

    for(i=2;i*i<=1000000;i++)
        if(!ciur[i])
            for(j=i*i;j<=1000000;j+=i)
                ciur[j]=1;

    for(i=2;i<=1000000;i++)
        if(!ciur[i])
        {
            k++;
            nrprim[k]=i;
        }

}

void Descompunere()
{
    int d=1;
    while(b>1 && nrprim[d]*nrprim[d]<=b && d<=k)
    {
        if(b%nrprim[d]==0)
        {
            divb[++nrdiv]=nrprim[d];

            while(b%nrprim[d]==0)
                b/=nrprim[d];
        }
        d++;
    }

    if(b>1)divb[++nrdiv]=b;
}

void Back(int k)
{
    if(k==nrdiv+1)
    {
        nr1=0;
        s=1;

        for(int i=1;i<=nrdiv;i++)
            if(x[i]==1)
            {
                nr1++;
                s=s*divb[i];
            }

        if(nr1)
        {
            if(nr1%2==1)Stot+=a/s;
            else Stot-=a/s;
        }

        return ;
    }

    for(int i=0;i<=1;i++)
    {
        x[k]=i;
        Back(k+1);
    }
}

int main()
{
    fin>>Q;
    CIUR();

    while(Q--)
    {
        fin>>a>>b;
        nrdiv=0;
        Descompunere();

        Stot=0;
        Back(1);
        fout<<a-Stot<<"\n";
    }
    return 0;
}