#include <bits/stdc++.h>
using namespace std;
const int MAXP=1000000;
int M;
long long int A,B,card;
int x[20];
bool v[MAXP+1];
vector <int> prim;
vector <long long> p;

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++) {
        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;
        card = 0;
        bt(1, 1LL);
        g << A - card << '\n';
    }
    f.close();
    g.close();
    return 0;
}