#include<stdio.h>
long long a,b,s,h,e,y[1000001];
int k=1,j,l,t,m,i,v,r,u[1000001],p[1000001],x[80000];
int main() {
	freopen("pinex.in","r",stdin),freopen("pinex.out","w",stdout),scanf("%d",&m),x[1]=2;
	for(i=1;((i*i)<<1)+(i<<1)<1000001;i++)
	if(!(p[i>>3]&(1<<(i&7))))
      	for(j=((i*i)<<1)+(i<<1);(j<<1)+1<1000001;j+=(i<<1)+1)
            p[j>>3]|=(1<<(j&7));
	for(i=1;2*i+1<1000001;i++)
	if(!(p[i>>3]&(1<<(i&7))))
      	x[++k]=2*i+1;
	while(m--) {
		scanf("%lld%lld",&a,&b),l=0;
      	for(j=1,s=a;b>1&&x[j]*x[j]<=b;j++) {
      		for(e=b;e%x[j]==0&&e>1;e/=x[j]);
      		if(e<b)
      			y[++l]=x[j],b=e;
		}
      	if(b>1)
            y[++l]=b;
      	if(l) {
		  	for(i=1;i<=l;i++)
                s=s-a/y[i];
            for(i=2;i<=l;i++)
            for(t=1,u[1]=0;t;) {
                for(u[t]++,v=j=1;j<t&&v;j++)
				if(u[j]==u[t])
      				v=0;
                if(v)
                    if(u[t]<=l)
                        if(t==i) {
                            for(e=r=1;r<=i;r++)
                                e*=y[u[r]];
							s=(!(i&1))?(s+a/e):(s-a/e);
						}
                    	else
                            t++,u[t]=u[t-1];
                    else
                    	t--;
			}
		}
    	printf("%lld\n",s);
	}
}