#include<fstream>
#include<vector>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");

const int NMax = 1 << 18;

bool Prim[NMax + 5];
int X[64];
int A,B,M,N,P,Sol;

vector <int> Div;

void Sieve()
{
    for(int i = 2 ; i <= NMax ; ++i)
    {
        if(!Prim[i])
            for(int j = 2 * i ; j <= NMax ; j += i)
                Prim[j] = 1;
    }
}

void Back(int k)
{
    for(int i = X[k-1] + 1 ; i <= N ; ++i)
    {
        X[k] = i;

        P *= Div[X[k] - 1];

        if(k % 2)   Sol += A / P;
        else    Sol -= A / P;

        if(k < N)   Back(k + 1);

        P /= Div[X[k] - 1];
    }
}

void Solve()
{
    fin >> M;

    while(M--)
    {
        fin >> A >> B;

        for(int i = 2 ; i <= B / 2 ; ++i)
            if(!Prim[i] && !(B % i))
                Div.push_back(i);

        if(!Prim[B])    Div.push_back(B);

        N = Div.size(); P = 1; Sol = 0;

        Back(1);

        fout << A - Sol << "\n";

        Div.clear();
    }
}

int main()
{
    Sieve();
    Solve();

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