#include <fstream>
#include <math.h>
using namespace std;
bool Ciur[1000001];
int Vmax,Nrp,Prime[80000],i,Fact[80000],k,t,j,Nr,M,w;
long long int A,B,Prod,Sol,Val;
int main()
{
    ifstream fin("pinex.in");
    ofstream fout("pinex.out");

    Ciur[0]=1;
    Ciur[1]=1;
    Vmax=1000000;
    Nrp=0;
    for(i=2;i<=Vmax;i++)
        if(Ciur[i]==0)
        {
            for(j=i+i;j<=Vmax;j+=i)
                Ciur[j]=1;
            Nrp++;
            Prime[Nrp]=i;
        }//if
    fin>>M;
    for(i=1;i<=M;i++)
    {
        fin>>A>>B;
        k=0;
        t=0;
        while(B>1)
        {
            k++;
            if(B%Prime[k]==0)
            {
                while(B%Prime[k]==0)
                    B=B/Prime[k];
                t++;
                Fact[t]=Prime[k];
            }//if
            if(Prime[k]>sqrt(B) and B>1)
            {
                t++;
                Fact[t]=B;
                B=1;
            }//if
        }//while
        Val=1<<t;
        Sol=0;
        for(j=1;j<=Val-1;j++)
        {
            Nr=0;
            Prod=1;
            for(w=0;w<=t-1;w++)
                if(((1<<w)&j)!=0)
                {
                    Nr++;
                    Prod=Prod*Fact[w+1];
                }//if
            if(Nr%2==0)
                Nr=-1;
            else
                Nr=1;
            if(Prod!=1)
                Sol+=1LL*Nr*(A/Prod);
        }//for j
        fout<<A-Sol<<'\n';
    }//for i

    fin.close ();
    fout.close();
    return 0;
}