#include <iostream>
#include <fstream>
#include <cmath>
#define NMAX 1000001

using namespace std;

ifstream in("pinex.in");
ofstream out("pinex.out");
int M;
long long int A, B;
long long int nr_p[80000], k = 0;
bool prime[NMAX];
long long int factp[30];
int r = 0;
long long int rez = 0;

void ciur()
{
    int lim = sqrt(NMAX);
    for (int i = 3; i <= lim; i+=2)
        if (!prime[i])
        {
            for (int j = i * i; j <= NMAX; j += (2 * i))
                prime[j] = true;
        }
    nr_p[++k] = 2;
    for (int i = 3; i <= NMAX; i+=2)
        if(!prime[i])
            nr_p[++k] = i;
}

void descomp(long long int b)
{
    int indx = 1;
    r = 0;
    while ((1LL * nr_p[indx] * nr_p[indx]) <= b)
    {
        if(b % (nr_p[indx] * 1LL) == 0)
        {
            while(b % (nr_p[indx] * 1LL) == 0)
                b /= (nr_p[indx] * 1LL);
            factp[++r] = nr_p[indx];
        }
        indx++;
        if(indx > k)
            break;
    }
    if (b != 1)
        factp[++r] = b;
}

void pinex()
{
    long long int r2 = (1 << r) - 1;
    long long int p = 1;
    int nr;
    rez = 0;
    for (long long int i = 1; i <= r2; i++)
    {
        nr = 0;
        p = 1;
        for (long long int j = 0; (1 << j) <= i; j++)
            if (i & (1 << j))
            {
                p *= factp[j + 1];
                nr++;
            }
        if (nr & 1)
            rez += (A / p);
        else
            rez -= (A / p);
    }
}

int main()
{
    ciur();
    in >> M;
    for (int i = 1; i <= M; i++)
    {
        in >> A >> B;
        descomp(B);
        pinex();
        out << A - rez << "\n";
    }
    in.close();
    out.close();
    return 0;
}