#include <stdio.h>
#include <fstream>
#include <vector>
#include <math.h>

using namespace std;

const long long _iMaxNumber =  1e12;
const int _iSqrtMaxNumber = 1e6+1;

class TEratosthenesSieve
{
   public:
        std::vector <int> m_vPrimes;

        TEratosthenesSieve(long long lldMaxNumber);
        ~TEratosthenesSieve();

        void PrintPrimes(FILE * fOut);
    protected:
        static const int s_iSieveLength = _iSqrtMaxNumber;
        char m_vSieve[s_iSieveLength];

        virtual void ComputeSieve(long long lldMaxValue);
        virtual void ReorderSieve(int iMaxValue);
    private:
        int InitSieve(int iMaxValue);
};

class TDivisors
{
    public:
        TDivisors(long long lldNumber, TEratosthenesSieve * objSieve);
        ~TDivisors();

        vector <int> m_vDivisors;

       friend ostream &operator<<(ostream &fOutput, TDivisors &objDivisor)
        {/*
            #ifndef INFOARENA
                std::vector<int>::iterator itIndex;

                for (itIndex=objElement.m_vData.begin(); itIndex!=objElement.m_vData.end(); ++itIndex)
                {
                    fOutput<<*itIndex;
                }
                fOutput << endl;
            #endif // INFOARENA
            fOutput << objElement.m_vData[objElement.iKthPosition];*/

            return fOutput;
        }
        long long ComputeNumbersLessThanAandPrimesWithB(long long lldNumberA, long long lldNumberB);
    private:
        TEratosthenesSieve * objSieve;

        int vBackArray[30];
        long long lldNumberA;

        void ComputeDivisors(long long lldNumbers);
        long long Back(int iK, int iLength, long long lldProductDivisors);
};

//---------------------------------------------------
//------------------TEratosthenesSieve---------------
//---------------------------------------------------
TEratosthenesSieve::TEratosthenesSieve(long long lldMaxNumber)
{
    lldMaxNumber=sqrt(lldMaxNumber);

    this->ComputeSieve(lldMaxNumber);
    this->ReorderSieve(lldMaxNumber);
}
//---------------------------------------------------
void TEratosthenesSieve::PrintPrimes(FILE * fOut)
{
    std::vector <int>::iterator itIndex;

    for (itIndex=this->m_vPrimes.begin(); itIndex!=this->m_vPrimes.end(); ++itIndex)
        fprintf(fOut,"%d ",*itIndex);
}
//---------------------------------------------------
void TEratosthenesSieve::ReorderSieve(int iMaxValue)
{
    for (int iIndex=2; iIndex<=s_iSieveLength; iIndex++)
        if (m_vSieve[iIndex]==0)
            m_vPrimes.push_back(iIndex);
}
//---------------------------------------------------
int TEratosthenesSieve::InitSieve(int iMaxValue)
{
    for (int iIndex=0; iIndex<=iMaxValue; iIndex++)
        m_vSieve[iIndex]=0;

    return 1;
}
//---------------------------------------------------
TEratosthenesSieve::~TEratosthenesSieve()
{
    this->m_vPrimes.clear();
    //delete[] m_vSieve;
}
//---------------------------------------------------
void TEratosthenesSieve::ComputeSieve(long long iMaxValue)
{
    this->InitSieve(iMaxValue);//init Sieve

    int iNumber;
    for (int i=2; i<iMaxValue; i++)
        if (m_vSieve[i]!=1)
        {
            iNumber = i+i;
            while (iNumber <= iMaxValue)
            {
                m_vSieve[iNumber]=1;
                iNumber += i;
            }
        }
}
//---------------------------------------------------
//--------------------TDivisors----------------------
//---------------------------------------------------
TDivisors::TDivisors(long long lldNumber, TEratosthenesSieve * objSieve)
{
    this->objSieve=objSieve;

    ComputeDivisors(lldNumber);
}
//---------------------------------------------------
TDivisors::~TDivisors()
{
    this->m_vDivisors.clear();
}
//---------------------------------------------------
void TDivisors::ComputeDivisors(long long lldNumber)
{
    std::vector <int>::iterator itIndex;
    int iSqrtNumber = sqrt(lldNumber), iExponent;

    for (itIndex=this->objSieve->m_vPrimes.begin(); itIndex!=this->objSieve->m_vPrimes.end(); ++itIndex)
    {

        if ((*itIndex>iSqrtNumber)||(lldNumber==1))
            break;

        iExponent=0;

        while (lldNumber % *itIndex == 0)
        {
            lldNumber/=*itIndex;

            iExponent++;
        }
        if (iExponent!=0)
        {
            this->m_vDivisors.push_back(*itIndex);
            iSqrtNumber = sqrt(lldNumber);
        }
    }

    if (lldNumber!=1)
    {
        this->m_vDivisors.push_back(lldNumber);
    }

}
//---------------------------------------------------
long long TDivisors::Back(int iK, int iLength, long long lldProductDivisors)
{
    long long lldValue=0;
    if (iK==m_vDivisors.size())
    {
        if (iLength == 0) return 0;

        if (iLength % 2 == 1) return this->lldNumberA/lldProductDivisors;
        else return -this->lldNumberA/lldProductDivisors;

    } else
    {
        vBackArray[iK]=0;
        lldValue+=Back(iK+1,iLength,lldProductDivisors);

        vBackArray[iK]=1;
        lldValue+=Back(iK+1,iLength+1,lldProductDivisors*this->m_vDivisors[iK]);
    }
    return lldValue;
}
//---------------------------------------------------
long long TDivisors::ComputeNumbersLessThanAandPrimesWithB(long long lldNumberA, long long lldNumberB)
{
    //long long lldResult=0, lldCardinal;
    this->lldNumberA=lldNumberA;

    return lldNumberA - Back(0,0,1);

    /*
    for (int iIndex=0; iIndex<this->m_vDivisors.size(); iIndex++)
    {
        lldCardinal = lldNumberA / m_vDivisors[iIndex]l;
        lldResult+=lldCardinal;
    }

    return lldResult;*/
}
//---------------------------------------------------
//---------------------------------------------------
//---------------------------------------------------
void ReadData(TEratosthenesSieve* objSieve)
{
    ifstream fin ("pinex.in");
    ofstream fOut ("pinex.out");

    int iCount;

    fin>>iCount;

    long long lldNumberA,lldNumberB;
    for (int iIndex=0; iIndex<iCount; iIndex++)
    {
        //fscanf(fIn,"%lld",&lldNumber);
        fin>>lldNumberA>>lldNumberB;

        TDivisors * objDivisors = new TDivisors(lldNumberB,objSieve);
        //fprintf(fOut,"%lld",objDivisors->ComputeNumbersLessThanAandPrimesWithB(lldNumberA,lldNumberB));
        fOut << objDivisors->ComputeNumbersLessThanAandPrimesWithB(lldNumberA,lldNumberB);
        fOut << endl;
        //fOut << 423;


        //fprintf(fOut,"\n");
        objDivisors->~TDivisors();
    }

    fOut.close();

}
//---------------------------------------------------
int main()
{
    TEratosthenesSieve* objSieve = new TEratosthenesSieve(1e12);

    FILE * fOut;// = fopen("pinex.out","w");

    //objSieve->PrintPrimes(fOut);
    ReadData( objSieve);

    //fclose(fOut);

    objSieve->~TEratosthenesSieve();

    return 0;
}