#include <fstream>
#include <vector>
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
int m,p,x,nrd,d[15];
const int dim=1e6;
long long a,b,s;
bool ciur[dim+3];
vector<int>nrp;
void back(int k,int last){
    if(k==nrd+1){
        if(nrd%2==0)
            s-=a/x;
        else
            s+=a/x;
    }else{
        if(k>1){
            if((k-1)%2==0)
                s-=a/x;
            else
                s+=a/x;
        }
        for(int i=last+1;i<=nrd;i++){
            x*=d[i];
            back(k+1,i);
            x/=d[i];
        }
    }
}
int main()
{
    cin>>m;
    ciur[1]=ciur[0]=1;
    for(int i=2;i<=dim;i++)
        if(ciur[i]==0){
            nrp.push_back(i);
            for(int j=2*i;j<=dim;j+=i)
                ciur[j]=1;
        }
    while(m--){
        s=0;
        cin>>a>>b;
        nrd=0;
        for(int i=0;nrp[i]*nrp[i]<=b;i++)
            if(b%nrp[i]==0){
                d[++nrd]=nrp[i];
                while(b%nrp[i]==0)
                    b/=nrp[i];
            }
        if(b!=1)
            d[++nrd]=b;
        x=1;
        back(1,0);
        cout<<a-s<<'\n';
    }
    return 0;
}