#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

typedef unsigned long long LL;
const int MAXN = 1000000;

LL A, B;
LL Ans;
bool Prim[MAXN + 10];
int st[40];
LL Fact[40];
vector <LL> Prime;

void Ciur ()
{
    int i, j;

    Prime.push_back (2);

    for (i = 3; 1ULL * i * i <= MAXN; i += 2)
        if (!Prim[i]){
            Prime.push_back (i);

            for (j = i * i; j <= MAXN; j += (2 * i))
                Prim[j] = 1;
        }
}

void update (int lev, LL prod)
{
    if (lev & 1)
        Ans += (A / prod);
    else
        Ans -= (A / prod);
}

void back (int lev, LL prod)
{
    update (lev, prod);
    int i;

    for (i = st[lev - 1] + 1; i <= Fact[0]; i ++){
        st[lev] = i;
        if ((unsigned long long) prod * Fact[i] > A)
            continue;
        back (lev + 1, (unsigned long long) 1ULL * prod * Fact[i]);
    }
}

LL Solve ()
{
    int i = 0, N;
    N = Prime.size ();

    while (B > 1 && i < N){
        if (B % Prime[i] == 0){
            Fact[++ Fact[0]] = Prime[i];

            while (B % Prime[i] == 0)
                B /= Prime[i];
        }
        i ++;
    }

    if (B > 1)
        Fact[++ Fact[0]] = B;

    back (1, 1);
    return Ans;
}

int main()
{
    int T;

    Ciur ();

    for (in >> T; T; T --){
        in >> A >> B;
        Ans = 0;
        Fact[0] = 0;
        out << Solve () << "\n";
    }

    return 0;
}