#include <fstream.h>
void main()
{ long long n,i,s,a[1000],j,cj,r,copie;
fstream f1("sum.in",ios::in);
fstream f2("sum.out",ios::out);
f1>>n;
for (i=1;i<=n;i++)
	f1>>a[i];
for (i=1;i<=n;i++)
	{
	s=1;
	for (j=2;j<2*a[i];j++)
		{
		copie=a[i];
		cj=j;
		while(a[i]%j!=0)
			{
			r=a[i]%j;
			a[i]=j;
			j=r;
			}
		if (j==1) s=s+cj;
		j=cj;
		a[i]=copie;
		}
	f2<<s<<endl;
	}
}