#include <cstdio>
#include <vector>
#define NMAX 1000005
using namespace std;

FILE *in=fopen("pinex.in","r");
FILE *out=fopen("pinex.out","w");


long long n,s,A;
vector <bool> fv;
bool prime[NMAX];
vector <int> pri;

void ciur()
{
  for(int i = 2; i <= NMAX; ++i)
  {
    if(prime[i] == 0)
    {
      pri.push_back(i);
      for(int j = i + i; j <= NMAX; j+=i)
        prime[j] = 1;
    }
  }
}


void descompunere(long long x, vector <long long> &v)
{
    int ct=0,f,e=0;
    f=pri[ct++];
    while(x!=1&&f*f<=x)
    {
        e=0;
        while(x%f==0)
        {
            e++;
            x/=f;
        }
        if(e)
            v.push_back(f);
        f=pri[ct++];
    }
    if(x!=1)
        v.push_back(x);
}

void bk(vector<long long> f)
{
    if(fv.size()==f.size())
    {
        int p=1,ct=0;
        for(int i=0;i<fv.size();i++)
            if(fv[i])
            {
                p*=f[i];
                ct++;
            }
        if(ct)
        {
        if(ct%2==1)
            s+=A/p;
        else s-=A/p;
        }
    }
    else{
            for(int i=0;i<=1;i++)
            {
                fv.push_back(i);
                bk(f);
                fv.pop_back();
            }
    }
}

int main()
{
    fscanf(in,"%lld",&n);
    ciur();
    while(n)
    {
        long long y;
        s=0;
        vector <long long> factori;
        fscanf(in,"%lld%lld",&A,&y);
        descompunere(y,factori);
        bk(factori);
        while(!fv.empty())
            fv.pop_back();
        fprintf(out,"%lld\n",A-s);
        n--;
    }
    return 0;
}