#include<stdio.h>
#define ll long long
int v[15],k,st[15];
ll a,nr;
void descompunere(int n){
    int i=2;
    k=0;
    while(n!=1){
        if(n%i==0)
            v[++k]=i;
        while(n%i==0)
            n/=i;
        i++;
    }
}
int valid(int x,int n){
    int nr=0;
    for(int i=1;i<=x;i++)
        if(st[i]==1)
            nr++;
    if(nr>k)
        return 0;
    if(n-x<k-nr)
        return 0;
    return 1;
}
void afisare(int n){
    ll p=1;
    for(int i=1;i<=n;i++)
        if(st[i]==1)
            p*=v[i];
    if(n%2==0)
        nr-=a/p;
    else
        nr+=a/p;
}
void back(int n,int k){
    if(k==n+1)
        afisare(n);
    else
        for(int i=0;i<=1;i++){
            st[k]=i;
            if(valid(k,n))
                back(n,k+1);
        }
}
int main(){
    int i,n;
    ll b;
    freopen("pb.in","r",stdin);
    freopen("pb.out","w",stdout);
    scanf("%d",&n);
    for(int l=1;l<=n;l++){
        nr=0;
        scanf("%I64d%I64d",&a,&b);
        descompunere(b);
        for(i=1;i<=k;i++)
            nr+=a/v[i];
        for(i=2;i<=k;i++)
            back(i,0);
        printf("%I64d\n",a-nr);
    }
    return 0;
}