/// VARIANTA 2
#include <fstream>
using namespace std;

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

const int NMAX = 78600,
          PMAX = 1000000,
          NDIV = 15;

int M;
long long A, B, card;

bool v[PMAX + 1];
int prim[NMAX+1], np;

long long p[NDIV];
int x[NDIV], lg;

void Eratostene(int n) {
    for (int i=3; i*i <= n; i+=2)
        if (v[i] == 0)
            for (int j=i*i; j<=n; j += 2*i)
                v[j] = 1;

    prim[++np] = 2;
    for(int i=3; i<=n; i+=2)
        if (v[i] == 0)
            prim[++np] = i;
}

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

void backTracking(int k, long long prod) {
    long long t1, t2;
    for (int i = x[k-1]+1; i <=lg; i++) {
        x[k] = i;
        t1 = prod * p[i];
        t2 = A / t1;
        if (k % 2 == 0)
            card -= t2;
        else
            card += t2;
        backTracking(k+1, t1);
    }
}

int main()
{
    Eratostene(PMAX);
    f >> M;
    while(M--) {
        f >> A >> B;
        generareDivizoriB();
        card = 0;
        backTracking(1, 1LL);
        g << A - card << '\n';
    }
    f.close();
    g.close();
    return 0;
}