#include <fstream>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
const int NMax = 1000000;
bool P[NMax + 5];
int Prime[NMax + 5];
int X[20],N,Divisor[20];
int M,NPrimes,Sign;
long long Product = 1,Sol,A,B;
void Back(int k)
{
    for(int i = X[k-1] + 1; i <= N; ++i)
    {
        X[k] = i;
        if(k % 2 == 0)
            Sign = -1;
        else
            Sign = 1;
        Product = Product * Divisor[X[k]];
        Sol = Sol + Sign*(A / Product);
        if(k < N)
        {
            Back(k+1);
        }
        Product = Product / Divisor[X[k]];
    }
}

void Sieve()
{
    for(int i = 2; i <= NMax; ++i)
        if(P[i] == 0)
        {
            Prime[++NPrimes] = i;
            for(int j = i + i; j <= NMax; j += i)
                P[j] = 1;
        }
}

void Decompose(int B)
{
    N = 0;
    for(int i = 1; i <= NPrimes; ++i)
    {
        int Exp = 0;
        while(B % Prime[i] == 0)
        {
            B = B / Prime[i];
            Exp++;
        }
        if(Exp)
            Divisor[++N] = Prime[i];
    }
    if(B != 1)
        Divisor[++N] = B;
}

int main()
{
    Sieve();
    fin >> M;
    while(M--)
    {
        fin >> A >> B;
        Decompose(B);
        Sol = 0; Product = 1;
        Back(1);
        fout << A - Sol << "\n";
    }
    return 0;
}