#include<stdio.h>
long long int  n,k,d,m,i,k1;
int main()
{
FILE *f,*g;
f=fopen("sum.in","r");
g=fopen("sum.out","w");
fscanf(f,"%lld",&n);
for(i=1;i<=n;i++)
{ 
	fscanf(f,"%lld",&k);
	d=2;m=k;k1=k;
	if(m%d==0)
		{
		while(m%d==0)m/=d;
		k/=d;
		k*=d-1;
		}
	for(d=3;d*d<=m;d=d+2)
		if(m%d==0)
			{
			while(m%d==0)m/=d;
			k/=d;
			k*=d-1;
			}
	if(m>1)
		{k/=m;k*=m-1;}
	k1*=k;
	fprintf(g,"%lld",k1);
}
fcloseall();
return 0;
}#include<stdio.h>
#include<math.h>
int x,y,a,b,a1,b1,i,t,j,k;
int prime(int a, int b)
{   int d;
    if(a==1||b==1) return 1;
     else if(b%a==0) return 0;
             else while(a==b) if(a>b) a-=b;
		                            else b-=a;

    if(a==1) return 1;
    return 0;
 }
int main()
{  FILE *f=fopen("divmul.in","r"),
        *g=fopen("divmul.out","w");
   fscanf(f,"%d",&t);
   for(j=1;j<=t;j++)
   {  fscanf(f,"%d%d",&x,&y);
      k=0;
      for(a1=1;a1<=sqrt(y/x);a1++)
        if((y/x)%a1==0)
          { b1=y/(x*a1);
            if(prime(a1,b1))  k++;
            }
      fprintf(g,"%d\n",k*2);
    }
      fcloseall();
      return 0;
}