#include <iostream>
#include <fstream>

using namespace std;

const int dim=1000000;
int nrprim[dim+5],k,d[dim+5];

bool ciur[dim+5];

void exec_ciur()
{
    for (int i=2; i<=dim; i++)
        ciur[i]=true;
    for (int i=2; i<=dim; i++)
        if (ciur[i]==true)
        {
            nrprim[++k]=i;
            for (int j=i+i; j<=dim; j+=i)
                ciur[j]=false;
        }
}

long long int prelucrare(long long int a,long long int b)
{
    int nrd=0;
    for (int i=1; 1LL*nrprim[i]*nrprim[i]<=b; i++)
        if (b%nrprim[i]==0)
        {
            d[++nrd]=nrprim[i];
            while(b%nrprim[i]==0)
                b/=nrprim[i];
        }
    if (b!=1)
    {
        d[++nrd]=b;
    }
    long long int rez=0;
    for (int i=1; i<=nrd; i++)
        rez+=a/d[i];
    for (int i=1; i<=nrd-1; i++)
        for (int j=i+1; j<=nrd; j++)
            rez-=a/(1LL*d[i]*d[j]);
    for (int i=1; i<=nrd-2; i++)
        for (int j=i+1; j<=nrd-1; j++)
            for (int l=j+1; l<=nrd; l++)
                if (i%2)
                    rez+=a/(1LL*d[i]*d[j]*d[l]);
                else
                    rez-=a/(1LL*d[i]*d[j]*d[l]);
    return a-rez;
}

int main()
{
    ifstream fin ("pinex.in");
    ofstream fout ("pinex.out");
    exec_ciur();
    int m;
    fin>>m;
    for (int var=1; var<=m; ++var)
    {
        long long int a,b;
        fin>>a>>b;
        fout<<prelucrare(a,b)<<'\n';
    }
    return 0;
}