#include <fstream>
#include <vector>

using namespace std;

/// 100p
const int MAXP = 10000000;  // Margine superioară pentru cel mai mare număr prim

int M;  // Datele de intrare
long long int A, B, card;
int x[20];

bool v[MAXP + 1];        // Vector pentru Ciurul lui Eratostene
vector<int> prim;        // Vectorul numerelor prime
vector<long long> p;     // Vectorul divizorilor primi ai lui B

ifstream f("pinex.in");
ofstream g("pinex.out");

void generareNumerePrime(int n)
{
    int i, j;
    for (i = 3; i * i <= n; i += 2)
    {
        if (v[i] == 0)
        {
            for (j = i * i; j <= n; j += 2 * i)
                v[j] = 1;
        }
    }
    prim.push_back(2);
    for (i = 3; i <= n; i += 2)
    {
        if (v[i] == 0)
            prim.push_back(i);
    }
}

void generareDivizoriB()
{
    p.clear();
    for (int i = 0; 1LL * prim[i] * prim[i] <= B; i++)
    {
        if (B % prim[i] == 0)
        {
            p.push_back(prim[i]);
            do
            {
                B /= prim[i];
            }
            while (B % prim[i] == 0);
        }
    }
    if (B > 1) p.push_back(B);
}

void bt(int k, long long prod)
{
    long long t1, t2;
    for (int i = x[k - 1] + 1; i < (int)p.size(); i++)    // (*) Iterates through prime factors of B
    {
        x[k] = i;
        t1 = prod * p[i];
        t2 = A / t1;
        if (k % 2 == 0)
            card -= t2;
        else
            card += t2;
        bt(k + 1, t1);
    }
}

int main()
{
    generareNumerePrime(MAXP);
    f >> M;
    while (M--)
    {
        f >> A >> B;
        generareDivizoriB();

        x[0] = -1;  // artificiu pentru (*)
        card = 0;
        bt(1, 1LL);

        g << A - card << '\n';
    }
    f.close();
    g.close();
    return 0;
}