#include <fstream>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int t,ciur[1000001],nr,v[80000],fac[30],nrf;
long long a,b;
int main()
{
    fin>>t;
    ciur[0]=ciur[1]=1;
    for(int i=1;i<=1000000;i++)
    {
        if(ciur[i]==0)
        {
            nr++;
            v[nr]=i;

            for(int j=i+i;j<=1000000;j+=i)
            {
                ciur[j]=1;
            }
        }
    }
    for(int p=1;p<=t;p++)
    {
        fin>>a>>b;
        long long sol=0;
        nrf=0;

        for(int d=1;v[d]*v[d]<=b && d<=nr;d++)
        {

            if(b%v[d]==0)
            {

                nrf++;
                fac[nrf]=v[d];
                 while(b%v[d]==0 && b!=1)
            {

                b=b/v[d];


            }
            }


        }


        if(b!=1)
        {

            nrf++;
            fac[nrf]=b;
        }



        int l=(1<<nrf)-1;
        for(int i=1;i<=l;i++)
        {
            long long prod=1;
            long long nrcif=0;
            for(int p=0;p<nrf;p++)
            {
                if((i>>p)&1)
                {
                    nrcif++;
                    prod=prod*fac[p+1];
                }
            }
            int coef=1;
            if(nrcif%2==0)
                coef=-1;
            sol=sol+coef*(a/prod);

        }
        fout<<a-sol<<"\n";

    }

    return 0;
}