#include<cstdio>
using namespace std;

const int NMAX=30;
const int MMAX=1000005;
long long factori[NMAX];
int ind,prim[80000],indice;
bool ciur[MMAX];

void ciurul(){
    for(int i=2;i*2<=MMAX;i++)
        ciur[i*2]=1;
    for(int i=3;i*i<=MMAX;i+=2)
        if(!ciur[i])
            for(int j=i*i;j<=MMAX;j+=2*i)
                ciur[j]=1;
    for(int i=2;i<=MMAX;i++)
        if(!ciur[i])
            prim[++indice]=i;
}

void det_fact(long long b){
    long long cb=b;
    for(int i=1;i<=indice && b>1 && prim[i]*prim[i]<=cb;i++)
        if(b%prim[i]==0){
            factori[++ind]=prim[i];
            while(b%prim[i]==0)
                b/=prim[i];
        }
    if(b>1)
        factori[++ind]=b;
}

long long det_card(long long a){
    long long p=1<<ind;
    long long s=0;
    for(long long v=1;v<p;v++){
        long long nr=1,paritate=0;
        for(int i=0;i<ind;i++)
            if((1<<i) & v){
                nr*=factori[i+1];
                paritate++;
            }
        long long card=a/nr;
        if(paritate%2)
            s+=card;
        else
            s-=card;
    }
    return s;
}

void reset(){
    for(int i=1;i<=ind;i++)
        factori[i]=0;
    ind=0;
}

int main(){
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    int m;
    long long a,b;
    scanf("%d", &m);
    ciurul();
    for(int i=1;i<=m;i++){
        scanf("%lld%lld", &a, &b);
        det_fact(b);
        printf("%lld\n", a-det_card(a));
        reset();
    }
    return 0;
}