#include <iostream>
#include <fstream>

using namespace std;

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

bool ciur[dim];

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;
        }
}

int prelucrare(long long int a,long long int b)
{
    int nrd=0;
    for (int i=1;nrprim[i]<=b;i++)
        if (b%nrprim[i]==0)
            d[++nrd]=nrprim[i];
    /*for (int i=1;i<=nrd;i++)
        cout<<d[i]<<' ';
    cout<<endl;*/
    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/(d[i]*d[j]);
    for (int i=1;i<=nrd-2;i++)
        for (int j=i+1;j<=nrd-1;j++)
            for (int k=j+1;k<=nrd;k++)
                if (i%2)
                    rez+=a/(d[i]*d[j]*d[k]);
                else
                    rez-=a/(d[i]*d[j]*d[k]);
    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;
}