HDU1286

hdu1286.cpp

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define sd(x) scanf("%d",&x)
#define sdd(x,y) scanf("%d%d",&x,&y)
#define sddd(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define slflf(x,y) scanf("%lf%lf",&x,&y)
#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
using namespace std;

int eular(int n)
{
	int ret = 1, i;
	for (i = 2; i * i <= n; i++)
		if (n % i == 0)
		{
			n /= i;
			ret *= (i - 1);
			while (n % i == 0)
			{
				n /= i;
				ret *= i;
			}
		}
	if (n > 1)
		ret *= (n - 1);
	return ret;
}

int main(void)
{
	int t;
	sd(t);
	while (t--)
	{
		int n; sd(n);
		printf("%d\n", eular(n));
	}
	return 0;
}