#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#define ct 100000
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int T,A,B,k;
long long prod=1,vr=0,sol=0,q=1;
bool viz[100011];

set<long long> h[100011];
set<long long>::iterator it;

struct nrprime{
    int x,p;
};
nrprime prim[100011];

bool cautare(int val){
    it=h[val%ct].find(val);
    if(*it)
        return true;
    else
        return false;
}

void track(){
    if(!cautare(prod)){
        h[prod%ct].insert(prod);
        if(q%2)
            sol+=(A/prod);
        else
            sol-=(A/prod);
    }
    for(register int i=1;i<=k;i++){
        if(!viz[i]){
            viz[i]=true;
            q++;
            prod*=prim[i].x;
            track();
            prod/=prim[i].x;
            q--;
            viz[i]=false;
        }
    }
}

int main(void){
    register int i,j,t,fin,st;

    f>>T;
    for(;T>0;T--){
        f>>A>>B;
        if(B==1 || A==1){
            g<<"0\n";
            continue;
        }
        for(i=1;i<=ct;i++)
            h[i].clear();
        k=0,sol=0;
        for(i=2;i<=sqrt(B) && B!=1;i++){
            if(B%i==0)
                prim[++k].x=i,prim[k].p=1;
            while(B%i==0)
                B/=i;
        }
        if(B!=1){
            prim[++k].x=B;
            prim[k].p=1;
        }
        track();
        g<<sol<<"\n";
    }

    f.close();
    g.close();
    return 0;
}