#include <fstream>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
const int NMax = 1000000;
bool p[NMax + 5];
int Prim[NMax/10],K,N,A,B,Value;
long long Sol = 0; int X[20];
int Factor[NMax/10];
void Sieve()
{
    for(int i = 2; i <= NMax; ++i)
    {
        if(p[i] == 0)
        {
            Prim[++K] = i;
            for(int j = i + i; j <= NMax;  j+=i)
                p[j] = 1;
        }
    }
}

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

        if(k%2)
        {
            Sol += Value/Factor[X[k]];
        }


        else
        {
            Sol -= Value/Factor[X[k]];
        }


        if(k < N)
        {
            int OldValue = Value;
            Value = Value/Factor[X[k]];
            Back(k+1);
            Value = OldValue;
        }
    }
}

int main()
{
    int M;
    Sieve();
    fin >> M;
    while(M--)
    {
        fin >> A >> B; N = 0;
        for(int i = 1; (1LL * Prim[i] * Prim[i] <= B) && i <= K; ++i)
        {
            int e = 0;
            while(B % Prim[i] == 0)
            {
                B = B / Prim[i];
                e++;
            }
            if(e)
                Factor[++N] = Prim[i];
        }
        if(B != 1)
            Factor[++N] = B;


        Value = A; Sol = 0;


        Back(1);

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


    }
    return 0;
}