#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;

}