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

const int NMax = 1000000;

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

bitset <NMax + 5> Bit;
vector <int> Div;

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

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

        P *= Div[X[k]];

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

        if(k < (int) Div.size())  Back(k + 1);

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

void Solve()
{
    fin >> M;   X[0] = -1;

    while(M--)
    {
        fin >> A >> B;  Div.clear();

        for(int i = 1 ; Prim[i] * Prim[i] <= B && Prim[i]; ++i)
        {
            if(!(B % Prim[i]))    Div.push_back(Prim[i]);
            while(!(B % Prim[i])) B /= Prim[i];
        }

        if(B > 1)   Div.push_back(B);

        P = 1; Sol = 0;

        Back(1);

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

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

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