#include <fstream.h>
using namespace std;
int main()
{ long long n,i,s,a[10000],j,cj,r,copie;
ifstream f1("sum.in");
ofstream f2("sum.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<<"\n";
	}
return 0;
}