#include <iostream>
#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;

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

long long p[NDIV];
int 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 calcSol() {
    int nt = 1 << lg;
    long long card = 0, prod, t;
    for (int i=1; i<nt; i++) {
        prod = 1;
        int j = 0, p2, ndiv = 0;
        while((p2 = 1 << j) <= i) {
            if (p2 & i) {
                prod *= p[j + 1];
                ndiv++;
            }
            j++;
        }
        t = A / prod;
        if (ndiv % 2 == 0)
            card -= t;
        else
            card += t;
    }
    g << A - card << '\n';
}

int main()
{
    Eratostene(PMAX);
    f >> M;
    while(M--) {
        f >> A >> B;
        generareDivizoriB();
        calcSol();
    }
    f.close();
    g.close();
    return 0;
}