#include <iostream>
#include <fstream>
#include <vector>

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

int m;// a[501], b[501];
bool primi[1000001];
std::vector<int> nrPrime;

void setPrimi()
{
    for(int i = 2; i < 1000001; i++)
    {
        primi[i] = true;
    }

    for(int i = 2; i < 1000001; i++)
    {
        if(primi[i])
        {
            nrPrime.push_back(i);

            int j = i + i;
            while(j < 1000001)
            {
                primi[j] = false;
                j += i;
            }
        }
    }
}

//bool checkBinary(long long nr)
//{
//    if()
//}

void check(int x, int y)
{
    int i = 0;
    std::vector<int> myPrim;
    while(nrPrime[i] <= y)
    {
        if(!(y % nrPrime[i]))
        {
            myPrim.push_back(nrPrime[i]);
        }
        i++;
    }


    long long sVal = 1<<myPrim.size();
    long long mySum = 0;
    for(int k = 1; k < sVal; k++)
    {
        long long imp = 1;
        long long apar = 0;
        for(int kk = 0; kk < myPrim.size(); kk++)
        {
//            if(checkBinary(k, kk))
//            {
//                imp = imp * myPrim[kk];
//                apar++;
//            }
            if(k & ((long long) 1 << kk))
            {
                imp = imp * myPrim[kk];
                apar++;
            }
            if(apar % 2 == 0)
            {
                imp = imp * (-1);
            }
        }
//        std::cout<<mySum<<' '<<x<<' '<<imp<<'\n';
        mySum = mySum + (x / imp);
    }
    myPrim.clear();

    fout<<x - mySum<<'\n';
}

void citire()
{
    fin>>m;
    int a, b;
    for(int i = 0; i < m; i++)
    {
        fin>>a>>b;
        check(a, b);
//        std::cout<<a[i]<<' '<<b[i]<<'\n';
    }
}

void rezolvare()
{
//    for(int i = 0; i < m; i++)
    {
//        std::cout<<a[i]<<' '<<b[i]<<": ";
//        check(a[i], b[i]);
    }
}

int main()
{
    setPrimi();
    citire();
//    rezolvare();
    return 0;
}