#include <iostream>
#include <fstream>

using namespace std;

const int dim=1000005;
int nrprim[dim+5],k,d[dim+5];

bool ciur[dim+5];

void exec_ciur()
{
    for (int i=2; i<=dim; i++)
        ciur[i]=true;
    for (int i=2; i<=dim; i++)
        if (ciur[i]==true)
        {
            nrprim[++k]=i;
            for (int j=i+i; j<=dim; j+=i)
                ciur[j]=false;
        }
}

long long int prelucrare(long long int a,long long int b)
{
    int nrd=0;
    for (int i=1; 1LL*nrprim[i]*nrprim[i]<=b; i++)
        if (b%nrprim[i]==0)
        {
            d[++nrd]=nrprim[i];
            while(b%nrprim[i]==0)
                b/=nrprim[i];
        }
    if (b!=1)
    {
        d[++nrd]=b;
    }
    /*long long int rez=0;
    for (int i=1; i<=nrd; i++)
        rez+=a/d[i];
    for (int i=1; i<=nrd-1; i++)
        for (int j=i+1; j<=nrd; j++)
            rez-=a/(1LL*d[i]*d[j]);
    for (int i=1; i<=nrd-2; i++)
        for (int j=i+1; j<=nrd-1; j++)
            for (int l=j+1; l<=nrd; l++)
                if (i%2)
                    rez+=a/(1LL*d[i]*d[j]*d[l]);
                else
                    rez-=a/(1LL*d[i]*d[j]*d[l]);
    return a-rez;*/
    int nrc;
    long long int rez=a,s;
    for(int i=1; i<(1LL<<nrd); i++)
    {
        nrc=0;
        s=1;
        for(int j=0; j<nrd; j++)
        {
            if(((1LL<<j)&i)!=0)
            {
                nrc++;
                s=s*d[j+1];
            }
        }
        if(nrc%2==1)
        {
            rez=rez-a/s;
        }
        else
        {
            rez=rez+a/s;
        }
    }
    return rez;
}

int main()
{
    ifstream fin ("pinex.in");
    ofstream fout ("pinex.out");
    exec_ciur();
    int m;
    fin>>m;
    for (int var=1; var<=m; ++var)
    {
        long long int a,b;
        fin>>a>>b;
        fout<<prelucrare(a,b)<<'\n';
    }
    return 0;
}