#include <bits/stdc++.h>

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");


long long cmmdc(long long a,long long b)
{
    long long c;
    while(b)
    {
        c=a%b;
        a=b;
        b=c;
    }
    return a;
}


long long m,pas,t,a,n,d,i,nr,produs,rez,j,sol,b,v[1010],prim[100100];
bool ciur[1000010];
int main()
{
    f>>m;


    for(d=2;d<=1000000;d++)
    {
        if(ciur[d]==0)
        {
            t++;
            prim[t]=d;
            for(i=d*d;i<=1000000;i=i+d)
                ciur[i]=1;
        }
    }


    for(int pas=1;pas<=m;pas++)
    {
        f>>a>>b;

        sol=0;
        n=0;
        i=1;
        while(prim[i]*prim[i]<=b)
        {
            if(b%prim[i]==0)
            {

                n++;
                v[n]=prim[i];
                while(b%prim[i]==0)b=b/prim[i];
            }
            i++;
        }

        if(b!=1){n++;v[n]=b;}


        for(i=1;i<(1<<n);i++)
        {
            nr=0;
            produs=1;
            rez=0;


            for(j=0;j<n;j++)
            {
                if((i&(1<<j))!=0)
                {
                    nr++;
                    produs=produs*v[j+1];
                    rez=cmmdc(rez,v[j+1]);
                }
            }
            if(nr!=1)rez=produs/rez;
            else rez=produs;


            if(nr%2==1){sol=sol+a/rez;}
            else sol=sol-a/rez;
        }
        g<<a-sol<<'\n';
    }
    return 0;
}