#include <iostream>
#include <fstream>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int m,i,j,nr,nrd,nr2,k;
bool ok;
long long p[1000005],d[1000005],a,b,s,p2;
int main()
{
    f>>m;
    nr=1;
    p[1]=2;
    for(i=3; i<=1000000; i+=2)
    {
        ok=true;
        for(j=1; j<=nr && ok && p[j]*p[j]<=i; j++)
            if(i%p[j]==0)
            {
                ok=false;
                break;
            }
        if(ok)
            p[++nr]=i;
    }
    for(i=1; i<=m; ++i)
    {
        f>>a>>b;
        s=0;
        nrd=0;


        for(j=1; j<=nr && b>1; j++)
        {
            ok=false;
            while(b%p[j]==0)
            {
                b/=p[j];
                ok=true;
            }
            if(ok)
                d[++nrd]=p[j];
        }
        if(b>1)
            d[++nrd]=b;

        for(j=1; j<(1<<nrd); ++j)
        {
            p2=1;
            nr2=0;
            for(k=0; k<nrd; ++k)

                if((j>>k)&1)
                {
                    p2*=d[k+1];
                    ++nr2;
                }



            if(nr2%2==1)
            s+=a/p2;
            else s-=a/p2;
        }
        g<<a-s<<'\n';
    }
    return 0;
}