#include <fstream>

using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int m,k,i,j,p;
bool ok[1000005];
long long a,b,d[1000005],prod,nr,s;

void ciur()
{
    long long i,j;

    ok[0]=true;
    for(i=1; i <=1000000; i+=(i<<1)+1)
        if(!ok[i])
            for(j=((i*i)<<1)+(i<<1); ((j<<1)+1)<=1000000; j+=(i<<1)+1)
                ok[j]=true;
}
void factori(int x,int &k)
{
    int i;
    if(x%2==0)
    {
        while(x>0&&x%2==0)
            x/=2;
        d[++k]=2;

    }

    for(i=1; ((i*i)<<1)+(i<<1)<=x; ++i)
        {if(!ok[i])
            {
                if(x%((i<<1)+1)==0)
                {
                    d[++k]=((i<<1)+1);
                }

            }
          if(x>1&& 1LL * (2*i+1) *(2*i+1)>x)
            break;  }
    if(x!=1)
      d[++k]= b;
}
int main()
{
    f>>m;
    ciur();
    for(i=1; i<=m; ++i)
    {
        f>>a>>b;
        s=0;k=0;
        factori(b,k);
        for(j=1;j<=(1<<k);++j)
        {
            prod=1;
            nr=0;
           for(p=0;p<k;++p)
             if((j>>p)&1)
              {
                prod=d[p+1]* 1LL * prod;
                nr++;}
           prod=a/prod;
           prod=a-prod;
           if(nr%2==0)
             s-=prod;
           else s+=prod;}
           g<<s<<'\n';



        }


    return 0;
}