#include<cstdio>
const int N=1000001,M=20000000;
long long v[N],p[N],a[101],i,j,o,x,y,s,r,d,k,t,m,l,q,z;
char u[M];
inline long long A()
{
  	long long s=0;
  	for(;u[q]<48;q++);
  	for(;u[q]>47;q++)
  		s=s*10+u[q]-48;
  	return s;
}
inline void S(long long x)
{
    int i,e[30];
    for(j=0;x;x/=10)
        e[j++]=x%10;
    for(i=j-1;i>=0;i--)
        u[z+i]=e[j-1-i]+48;
    u[z+j]=10,z+=j+1;
}
int main()
{
	freopen("pinex.in","r",stdin),freopen("pinex.out","w",stdout),fread(u,1,M,stdin);
	for(m=N-1,i=2,o=A();i<=m;i++)
		if(!v[i])
			for(p[++d]=i,j=i*i;j<=m;j+=i)
				v[j]=1;
	while(o--)
	{
		for(x=A(),y=A(),l=x,k=0,i=1;i*i<=y;i++)
			if(y%p[i]==0)
				for(a[++k]=p[i];y%p[i]==0;y/=p[i]);
		if(y>1)
			a[++k]=y;
		for(t=1<<k,i=1;i<t;i++)
		{
			for(r=1,s=j=0;j<k;j++)
				if((i&(1<<j))>0)
					s++,r*=a[j+1];
            l+=((s%2==0?1:-1)*x/r);
		}
		S(l);
	}
	fwrite(u,1,z,stdout);
}