#include<stdio.h>
using namespace std;
char ciur[1000010];
int prime[80000],div[30];
void ciurr(int nrmax){
    int prim=2,m;
    while(prim*prim<=nrmax){
        for(m=prim;m<=nrmax/prim;m++)
            ciur[m*prim]=1;
        prim++;
        while(ciur[prim]==1)
            prim++;
    }
    for(m=2;m<=nrmax;m++)
        if(ciur[m]==0){
            prime[0]++;
            prime[prime[0]]=m;
        }
}
int main (){
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    int n,i,b,j,nr,q;
    long long a,p,sol;
    scanf("%d",&n);
    ciurr(1000000);
    for(q=1;q<=n;q++){
        scanf("%lld%d",&a,&b);
        div[0]=0;
        for(i=1;prime[i]*prime[i]<=b&&i<=prime[0];i++)
            if(b%prime[i]==0){
                div[0]++;
                div[div[0]]=prime[i];
                while(b%prime[i]==0)
                    b/=prime[i];
            }
        if(b!=1){
            div[0]++;
            div[div[0]]=b;
        }
        sol=0;
        for(i=1;i<(1<<div[0]);i++){
            nr=0;
            p=1;
            for(j=0;j<div[0];j++)
                if((1<<j)&i){
                    p=p*div[j+1];
                    nr++;
                }
            if(nr%2==1)
                nr=1;
            else
                nr=-1;
            sol=sol+nr*(a/p);
        }
        sol=a-sol;
        printf("%lld\n",sol);
    }
    return 0;
}