#include <bits/stdc++.h>

using namespace std;

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

long long n,m,i,p,j,nr,A,B,t,ans,d,prim[100100],v[100100];
bool ciur[1000001];

int main()
{
    f>>n;

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

    for(i=2;i<=1000000;i++)
        if(ciur[i]==0)m++,prim[m]=i;

    for(int pas=1;pas<=n;pas++)
    {
        f>>A>>B;
        d=1;t=0;ans=0;
        while(prim[d]*prim[d]<=B)
        {
            if(B%prim[d]==0)
            {
                t++;
                v[t]=prim[d];
                while(B%prim[d]==0)B/=prim[d];
            }
            d++;
        }
        if(B!=1)t++,v[t]=B;


        for(i=0;i<(1<<t);i++)
        {
            p=1;nr=0;
            for(j=0;j<t;j++)
            {
                if((i&(1<<j)))nr++,p*=v[j+1];
            }

            if(nr>0)
            {
                if(nr%2==0)ans-=A/p;
                else ans+=A/p;
            }
        }

        g<<A-ans<<'\n';
    }
    return 0;
}