#include <fstream>
#include <cmath>
#define NMAX 1000005
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
long long i1,m,a,b,p,i,c,d,v[10000],j,nr,s,m1,ciur[NMAX],prim[NMAX],q;
int main()
{
    f>>m1;
    for(i=2;i<=NMAX;i++)
        if(ciur[i]==0)
        for(j=i+i;j<=NMAX;j=j+i)
        ciur[j]=1;
    for(i=2;i<=NMAX;i++) if(ciur[i]==0) prim[++q]=i;
    for(i1=1; i1<=m1; i1++)
    {
        s=0;
        f>>a>>b;
        d=2;
        p=0;
        c=b;
        for(i=1;prim[i]*prim[i]<=b;i++)
        if(b%prim[i]==0) {v[++p]=prim[i];while(b%prim[i]==0) b/=prim[i];}
        if(b>1) v[++p]=b;
        for(i=1; i<(1<<p); i++)
        {
            nr=0;
            m=1;
            for(j=0; j<p; j++)
                if(i&(1<<j))
                {
                    nr++;
                    m*=v[j+1];
                }
            if(nr%2) s+=a/m;
            else s-=a/m;
        }
        g<<a-s<<'\n';


    }
    return 0;
}