#include<cstdio>
using namespace std;

const int NMAX=30;
long long factori[NMAX];
int ind;

void det_fact(long long b){
    long long d=2,cb=b;
    while(d*d<=cb && b>1){
        if(b%d){
            d++;
            continue;
        }
        factori[++ind]=d;
        while(b%d==0)
            b/=d;
        d++;
    }
    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);
    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;
}