#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;
int f[80005], v[80005], sol[80005];
bool ciur[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;
        while(b!=1){
            d=v[k];
            if(b%d==0){
                sol[++m]=d;
                while(b%d==0)
                    b/=d;
            }
            k++;
            d=v[k];
            if(d*d>b && b!=1)
                d=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";
    }
}