#include <fstream>
#include <bitset>

using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
bitset <1000010> B;
long long a,b,F[100],sol;
int n,m,P[80000],k,i,j;
void ciur(),bkt(int,long long);
int main()
{
    f>>m;
    ciur();
    for(;m;m--)
    {
        f>>a>>b;
        n=0;sol=0;
        for(i=1;i<=k&&P[i]*P[i]<=b;i++)
            if(b%P[i]==0)
            {
                F[++n]=P[i];
                while(b%P[i]==0)
                    b/=P[i];
            }
        if(b>1)
            F[++n]=b;
        bkt(1,1);
        g<<sol<<'\n';
    }
    return 0;
}
void ciur()
{
    P[++k]=2;
    for(i=3;i<=1000;i+=2)
        if(!B[i])
        {
            P[++k]=i;
            for(j=i*i;j<=1000000;j+=2*i)
                B[j]=1;

        }
    for(;i<=1000000;i+=2)
        if(!B[i])
        P[++k]=i;
}
void bkt(int poz,long long d)
{
   if(poz==n+1)
   {
       sol+=a/d;
       return;
   }
   bkt(poz+1,d);
   bkt(poz+1,-d*F[poz]);
}