#include <iostream>
#include<fstream>
using namespace std;
const int MAXP=1000000,  ///margine sup pentru cel mai mare nr prim
          NMAX=78600,   ///margine sup pt numarul max de nr prime
          NDIV=15;      ///margine sup pt nr max de div;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

int m;
long long int a,b;
bool v[MAXP+1];
int prim[NMAX],lp;
long long int p[NDIV];
int lg;

void generarenrprim(int n)
{
    for(int i=3; i*i<=n; i+=2)
        if(v[i]==0)
            for(int j=i*i; j<=n; j+=2*i)
                v[j]=1;
    prim[++lp]=2;
    for(int i=3; i<=n; i+=2)
        if(v[i]==0) prim[++lp]=i;
    //cout<<lp;
}

void generaredivb()
{
    lg=0;
    for(int j=1;1LL*prim[j]*prim[j]<=b;j++)
        if(b%prim[j]==0)
    {
        p[++lg]=prim[j];
        do
            b/=prim[j];
        while(b%prim[j]==0);
    }
    if(b>1) p[++lg]=b;
}

void calcsol()
{
    int nt=1<<lg;
    long long int card=0,prod,t;
    for(int i=1;i<nt;i++)
    {
        prod=1;
        int j=0,p2,ndiv=0;
        while((p2=1<<j)<=i)
        {
            if(p2&i)
            {
                prod*=p[j+1];
                ndiv++;
            }
            j++;
        }
        t=a/prod;
        if(ndiv%2==0) card-=t;
        else
            card+=t;
    }
    fout<<a-card<<'\n';
}

int main()
{
    generarenrprim(MAXP);
    fin>>m;
    while(m--)
    {
        fin>>a>>b;
        generaredivb();
        calcsol();
    }

    fin.close();
    fout.close();
    return 0;
}