#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
long long i, j, n, m, k, d, produs, nr, raspuns, a, b, t, kk;
long long v[1000002], sol[1000002];
bool ciur[1000002], f[1000002];
int main() {
    cin>>t;
    n=0;
    for(i=2;i<=1000000;i++){
        if(ciur[i]==0){
            v[++n]=i;
            for(j=i+i;j<=1000000;j+=i)
                ciur[j]=1;
        }
    }
    for(kk=1;kk<=t;kk++){
        cin>>a>>b;
        k=1;
        m=0;
        for(i=1;v[i]*v[i]<=b && b!=1;i++){
            if(b%v[i]==0){
                sol[++m]=v[i];
                while(b%v[i]==0)
                    b/=v[i];
            }
        }
        if(b!=1)
            sol[++m]=b;
        memset(f, 0, sizeof(f));
        produs=1;
        raspuns=0;
        while(f[0]==0){
            i=m;
            while(f[i]==1)
                f[i]=0, i--;
            f[i]=1;
            if(i==0)
                break;
            produs=1;
            nr=0;
            for(i=1;i<=m;i++){
                if(f[i]==1){
                    produs=1LL*produs*sol[i];
                    nr++;
                }
            }
            if(nr%2)
                raspuns+=a/produs;
            else
                raspuns-=a/produs;
        }
        cout<<a-raspuns<<"\n";
    }
}